Nash - Scientific Computing with PCs (523165), страница 20
Текст из файла (страница 20)
First, we must allow for theprogram code and working storage needed by the operating system for its own functions. Increasingly— and we believe this is due in many cases to sloppy programming — the operating system is demandingsuch a large part of the memory that user programs will hardly fit. Besides allocating memory for userprograms, the operating system also controls its allocation RAM-disks, printer buffers, file I/O buffers,network facilities, or disk caches.The architecture of the processor, the electronic design of the PC, and the operating system will all definelimits on the amount of memory we can access and may exclude certain addresses.
The original IBM PCdesign has led to some annoying limitations on the amount of data that can be addressed in it and itssuccessors. Historically, the Intel 8080 processor used a 16-bit address space allowing for 65,536 or 64Kaddresses, each storing one byte of information. To partially overcome this address space limitation, aswitching scheme is used that allows several banks of 64K of memory to be used, but only one at a time.By appropriate programming we can then work with much larger amounts of memory, but at the cost ofdeveloping quite complicated software. A similar bank switching idea is used in the Intel 8088 processor(the processor of the original IBM PC and XT) that manages to combine a 16-bit address with a 16-bitsegment register.
The segment register is multiplied by 16 and added to the 16-bit regular or offset address(Scanlon, 1984), allowing for a total of 220 or 1,049,576 or 1 megabyte of memory. Where necessary, we willspecify the 20 bits as 5 hexadecimal digits rather than use the complicated segment:offset notation thatis not unique and confusing.52Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr.
Dobb’s JournalWhen IBM designed the original PC it was decided to further reduce the available memory for programs,including the operating system, to just 640K. The remaining addresses were reserved for ROMs, diskcontrollers, video adapters, and other devices.Programming languages may complicate the issue of memory. Many early compilers and interpreters forMS-DOS PCs used only a short form of addressing involving the offset address. This means that programshad to fit both code and data in a single block of 64K of code. A minor improvement made in thosecompilers allowing 64K for code and 64K for data. More modern compilers have fewer restrictions if thecorrect compiler and/or linker switches are set.
Read the manual carefully!More recent Intel processors, along with the Motorola 680x0 processors used in the Macintosh, can addressvery large amounts of memory directly. Unfortunately, there is much "old" but still useful MS-DOSsoftware around. Some mechanisms for running the "old" programs within a more flexible environmentare beginning to appear. There are also schemes that allow large address space software to be runalongside MS-DOS, e.g., Microsoft Windows and IBM OS/2. Other approaches involve the use of specialmemory management software such as the Phar Lap or other DOS extenders that allow programs to usethe large address space yet be launched normally from within DOS.Various utility programs, e.g., the MEM instruction in more recent versions of MS-DOS, will allow theuser to determine the maximum amount of regular memory available to programs and data.
For PCsbased on Intel 80386 or later processors, configuration adjustments supported by various memorymanagement software allow some functions to be moved to regions of the address space beyond the 640Klimit. Typically, the space available for user programs may be increased by 60 to 70K, which may beenough to allow us to avoid other measures.On the practical level, we can only truly find out the maximum size of programs and data structures byexperiment. Our recommendation is to perform such trials before making a commitment to a givenprogramming environment. By varying parameters that define the size of large arrays or other constructsin small test programs, we can quickly, if inelegantly, learn the outside limits on such structures.
Weillustrate the approach in Figure 7.1.1. Comments in the codes reveal our findings.7.2Choice or Adjustment of Data StructuresIf we cannot carry out a computational task by either reconfiguring our PC to gain more usable memoryor by adding physical memory, then we must reorganize the calculations. This essentially means choosingdifferent ways to store data or using a different method for solving the computational problem.
Here welook at the data structures.An obvious method for reducing the memory requirement of a task is to reuse a variable or array so thatit holds more than one piece or block of data at different stages of the calculation. This reuse of datastructures is a very common feature of many algorithms, especially those developed in the early years ofautomatic computation. It is easier said than done. First we must find out what data is needed at eachstage of a program and then arrange for it to be stored appropriately for use in calculations.Some programming languages allow certain data structures to be defined only for the duration of a givenblock of code.
Indeed, variables and arrays used in FORTRAN subroutines, which are not in the argumentlist (calling sequence) nor in COMMON, are supposed to be local and not defined when the subroutineis reentered (ANSI 1978). In practice, however, compiler writers may not bother arranging that memorybe released when not needed. It is simpler to assign space for each subroutine separately, even if the totalexceeds what is available. It is the user who must work to squeeze his or her program into the memoryavailable. C programming does allow for explicit allocation and release of memory, though it is stillcommon for programmers to forget to release storage.Early PCs had with user memory limited to about 30,000 bytes, so we reused even simple variables to7: SIZE DIFFICULTIES53keep programs as lean as possible.
However, bigger gains come from reuse or restructuring of arrays.Array space can be saved in the following ways:•Rectangular matrices should be dimensioned to conform to the problem. An array declared 20 by 10will have over 100 unused elements for a 12 by 8 problem. Some programming languages (e.g., C)allow dynamic redefinition. This needs to be done carefully.•An array may be reentered from disk rather than saved. For example, to solve linear equationsAx=b(7.2.1)we may decompose the matrix A. Such decompositions often overwrite the original matrix, so that noextra storage is needed. Once a solution x has been found, we no longer need the decomposition, and canreread the matrix into the same storage to compute the residualsr=b-Ax(7.2.2)•Matrix decompositions that have a special structure can employ different storage mechanisms (SeeSection 7.8).Arrays can also hold non-numeric data.
As with the examples just given, sensible choice of data structurescan save memory requirements.Figure 7.1.1Use of simple programs to determine array size limits.a) BASICb) PASCAL0 LET M = 1638520 DIM B(M)30 FOR I = 1 TO M40 LET B(I) = I50 NEXT I60 PRINT "DONE m="; M70 STOP80 REM for GWBASIC 3.23 m=1504790 REM for Turbo BASIC 1.1 m=16382100 REM for QBASIC 1.0, MS BASIC 6.0,QuickBASIC 4.00a m = 16383110 REM for TRUBASIC after conversion fromthis code m =37500120 REM was accepted, then it gave an out ofmemory error.program sizetest;constmaxsize = 8084; {biggest is 10808 in TP5.5}{ 8084 in TPW, but then runtime error 105 }{10809 in TP5.0}{10820 in TP3.01a TURBO.COM}{ 6487 in TP3.01a TURBOBCD.COM}{ 8114 in TP3.01a TURBO-87.COM}{vary the above number until programwill not work}varbig: array[1..maxsize] of real;i : integer;beginfor i:=1 to maxsize do big[i]:=i;writeln(’DONE SIZETEST for maxsize = ’,maxsize);end.7.3Usage MapIdeally, we would like data structures to be named for the data they hold.
When data is no longer needed,its corresponding data structure should be cleared so memory is freed. This is not always possible andso we reuse data structures, but then must keep track of what data elements are in each data structure— a source of possible confusion.To effectively reuse data structures, we must know when particular data elements are required and whentheir use has ended. A usage map is any record of the active data structures at some given programmilestones. We know of no programs that prepare such a map, but important aids are the cross-referencetable and the data dictionary (Section 6.1).
The usage map can become complicated when many dataidentifiers or program milestones are involved. It helps to group data elements in sets.The main task is to record the program milestone after which a given date element is not needed. Jumpsin the program (GOTOs) make this difficult to work out. We have found even well-structured programshave quite messy usage maps, and only recommend their preparation:54Copyright © 1984, 1994 J C & M M NashSCIENTIFIC COMPUTING WITH PCsNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaCopy for:Dr. Dobb’s Journal•Where we need to adapt a program to a slightly larger problem;•Where there are clear opportunities to reuse large data structures.Such retrospective attempts to reduce the space requirement of a program mean that the original designcould be improved.7.4RestructuringWhen the program and data will not fit, and reasonable chances for reuse of variables or arrays have beenexhausted, yet we still need a little more memory, restructuring the code to make it shorter may help.In particular, several sections of similar code may be replaced by subroutine calls to a single sub-program.Certain parts of a program that are nonessential to the calculation may be deleted or split into programsthat are to be chained with the main calculation (Section 7.6).
Output may be vastly simplified, even tothe detriment of readability, thereby saving the space of all the descriptive text in print commands. Twoor more loops over similar indices may be combined. Rather than use many assignment statements to putdata into variables or arrays, we can use special programming features or read values from a file.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
