Nash - Scientific Computing with PCs (523165), страница 22
Текст из файла (страница 22)
We may even want two copies of the vectors at hand with different orderingsof the elements.Example: 5 by 4 matrix10300•000010104020001r: 1c: 1v: 1142231313434521541The array is stored as a row-wise set of paired values giving the column-index and element value ofeach non-zero element. We can use two vectors C and V. A new row is indicated by a negativecolumn index. In this scheme, we can no longer present the matrix elements in any order. Clearly,column variants of this scheme are also possible. For the example above, we have (row form)7: SIZE DIFFICULTIEScvcomments-14-3-1-3-241113411"new" row, the first, column 1same row, column 4new row, row 2, column 3new row, row 3, column 1new row, row 4, column 3new row, row 5, column 2same row, row 5, column 459Previous Home Next60Copyright © 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 JournalChapter 8Timing Considerations8.18.28.38.48.58.6Profile of a programSubstitutionsSpecial hardwareDisk access timesTime/accuracy and other tradeoff decisionsTiming toolsSome applications of computation require answers within a specific time period. Any tracking problem,such as air or surface traffic control, satellite orbit management, or numerical machine tool positioning,must have answers quickly. How quickly may determine the hardware and/or software required for these"real-time" jobs. The machine must respond in a given elapsed time after receiving the data on whichcalculations are to be performed.Many other situations arise where timing is important.
Operators may lose interest and attention ifresponse is too slow. A timesharing scheduler may demote a "long" job to a low priority in the job queue,or may charge more than we wish to pay. While less than two decades ago, statements like:It is worthwhile thinking about a problem for an hour in order to save a minute of CPU time (Quittner,1977, p. 14)reflected genuine concerns, we can now buy high-performance processors for so low enough prices thatthe issue is now to speedup computations for our convenience rather than for computer efficiency.This chapter presents some techniques available to measure and reduce the execution time for a program.Because each problem has individual requirements, users must choose their own detailed path to attainacceptable speed.8.1Profile of a ProgramTo reduce the time requirement for a program we must know where time is spent.
We can measure thetime taken to execute a given segment of program code, count the number of times a given statement orgroup of statements is executed. We want to find the parts of the program that contribute most toexecution time.Such measurement of effort can be found from a profile of the entire program.
This will record thenumber of times a statement was executed. It may give a subsidiary count to show how often an IFstatement condition was TRUE or how many times a DO loop was entered or exited. Certain compilersmay allow this to be carried out by invoking special features. Sometimes programs exist that will carryout the profiling. They may even estimate the time taken by statements. We generally prefer to buildclocks or counters into programs ourselves to avoid high learning costs associated with other approaches,though we use the same ideas. We try to locate the time-critical portions of a program, not time every lineof source code. Focusing on known time-consuming tasks, we attempt to discover bottlenecks so we canseek to overcome them.
Some obvious features of our code to examine and time are loops, calls tosub-programs, and input/output functions.We can often speed up loops, especially nested loops (loops within loops) by streamlining their coding.8: TIMING CONSIDERATIONS61Common actions can be moved outside a loop. Note, however, the counter example in Monaghan (1992).Figure 8.1.1 gives examples of loop simplification.Some calls to subroutines or functions may be replaced by in-line code. A subroutine call may involvemuch work in transferring required information. Figure 8.1.2 gives an illustration in FORTRAN.Figure 8.1.1Illustration of loop simplification in cumulative binomial probability calculations.
Thecodes compute the probability we get k or fewer successes in n independent trials withprobability of success in a single trial of p.a) Explicit calculation.Note: C(n,i) = n!b) Partially simplified calculation using storedbinomial coefficients/ ((n-i)! i!)FA = 0.0DO 10 J=1,(K+1)LOOP FROM 0 TO K INCLUSIVEI=J-1FA=FA + C(N,I)* P**I * (1.0-P)**(N-I)CONTINUEC10C25CC30DO 25 J=1,KSTORING BINOMIAL COEFFICIENTSBCOEFF(J)=C(N,J)CONTINUENOW COMPUTE THE CUMULATIVE PROBABILITYQ = 1.0 - PQT = Q**NFB = QTIF (K.EQ.0) GOTO 40PT = P/QDO 30 I=1,KLOOP FROM 1 (NOT 0) TO K INCLUSIVEQT=QT*PTFB = FB + BCOEFF(I) * QTCONTINUEc) Calculation using a recurrence relation; no binomial coefficient calculation is carried out in this code.Q = 1.0 - PQT = Q**NFC = QTIF (K.EQ.0) GOTO 60PT=P/QDO 50 I=1,KLOOP FROM 1 (NOT 0) TO K INCLUSIVEQT = QT*(N-I+1)*PT/IFC = FC + QTCONTINUEC50Timings in seconds and cumulative probabilities for 5000 repetitions of the above calculations (LaheyF77L, 33MHz 80386/80387 MS-DOS PC).n82020k51010pT(a)FAT(b)FBT(c)0.3 2.470 0.9887078 1.760 0.9887078 0.440 0.98870780.9 5.930 0.0000072 4.450 0.0000072 0.770 0.00000720.1 5.930 0.9999993 4.450 0.9999992 0.770 0.9999994FC62Copyright © 1984, 1994 J C & M M NashSCIENTIFIC COMPUTING WITH PCsNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaFigure 8.1.2Copy for:Dr.
Dobb’s JournalEffects of algorithm, option selection and use of in-line code versus subroutine call forseveral FORTRAN programs for the singular value decomposition applied to randomsparse m by n matrices (many zeros)Method (see list below)mnIIIIIIV555866(4039)I550510194(6924)8751555866550510194875110510867(6539)1310312261(7838)1086720522503(14473)2940338707(18512)322162020405398950 1211600(249360)44862(24138)706101320400 1247400(954213)91839(22214)88329Timings are in microseconds for execution on an IBM 370/168 under the MVS operating system and theFORTRAN G1 compiler. The singular value decomposition of matrix A into the matrices U, S, and V maybe accomplished without the U matrix being computed explicitly.
Figures in brackets show the times forthis option.IIIIIIIV— the Golub/Reinsch method (see Wilkinson and Reinsch,1971)— a FORTRAN version of Nash (1979a), Algorithm 1— a FORTRAN version of Nash (1979a), Algorithm 4— method III using in-line code rather than a subroutine call to accomplish plane rotations of amatrixIf a sub-program executes too slowly, we may be able to substitute a quicker but less general version. Forexample, it is not necessary to use a general-purpose sub-program to compute results if the inputarguments have values in a specific range. Depending on requirements, we can replace the function callwith a table look-up or a simple approximation.
This is a time / accuracy tradeoff (Section 8.5).The action of printing data or reading or writing to disk or tape is generally very slow compared tomemory access, even with clever buffering schemes. It may be helpful to read data once into memoryif we have space, so that there is no waiting for disk access when we need to calculate. Printing can oftenbe postponed until a calculation is completed to avoid delaying progress within loops, or a print bufferused.The approach just presented is only one form of a trace of the program execution. Facilities for tracingexist within many programming environments and "debuggers". One needs to be a frequent user of suchtools to profit from their application.
Since each tool takes time and effort to learn, we prefer to add ourown trace when needed, but those who work with just one programming environment should know howto get the maximum information from its debugging, tracing or profiling tools.In Figure 8.1.3, we show the effect of reading data into an array in computing the mean and variance of10,000 numbers. Using standard formulas, a first pass over the data calculates the mean of the numbersand a second pass the variance and standard deviation. Alternatively we could a RAM-disk (Section 8.4)and avoid having to change our program.In carrying out profiling, the user may simply want to count the number of times a given operationoccurs. Simple count and write statements accomplish this.
Some examples, such as the number offunction or gradient evaluations in function minimization tasks, are so common as to be a regular partof packaged programs. Others can easily be added by the user. We note, in particular, the availability of8: TIMING CONSIDERATIONSFigure 8.1.363Variance calculation using standard two-pass formula on different MS-DOS computersfrom different disk types.a) Ratio time(data from disk) : time(data pre-read into array)b) Actual times (seconds) for using pre-read to array.64Copyright © 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 Journala count of floating-point operations within the MATLAB mathematical computation system (Moler, 1981,Math Works, 1992).One technique we have frequently used for following the progress of a program is to print different lettersor symbols whenever a particular segment of code is executed (Nash J C and Walker-Smith, 1987, p. 151and p. 167).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
