суперкомпьютер семейства ILLIAC (ILLInois Automated Computer), страница 3

Consider an example where m = 10; there are1024 points in the prime function. The formation of the elements of thevector B1 involves elements of Ak that are 512 samples apart. Eachelement of B2 is the sum of two elements of B1 that are 256 samples apartin the index, down to BI0, whose elements are the sum of neighboringelements in Bg.The equations for the vectors Bqrn are, writing the indices in theirfragmented formOn ILLIAC IV, the Ak elements are divided into 64 equal pieces. For theexample of 1024 time samples, there are 16 per Processing Element(PE).

The first PE contains the Ist, 65th, 129th, etc. time sample; thesecond PE contains the 2nd. 66th, 130th. etc. time sample, and so onthroughout all PE's. Computations for all but the last 5 steps are thereforecarried on within the individual PE's with no interaction between PE's. Forthe 5th from the last step, we must swap operands between PE's that are 32apart as indicated in the top layer of the accompanying figure. This is asimple route by distance 32. For the 4th from the last step, we must swapoperands between PE's that are 16 apart as indicated in the next to the toplayer of the figure. Half the operands are routed by a distance +16; half bya distance -16.

The third from last step routes half the operands by distance+8, half by distance -8. This continues through distances 4 and 2 to formthe results.As described above, the results are produced correctly, but in scrambledorder. Rearrangements of the data can be accomplished by fetching,routing, and storing. Approximately 160 or less route instructions arerequired to move the 1024 result points into their proper locations.Data Transfer Paths, Fast Fourier Transform(16 PE Example)TABLE LOOK-UPTable look-up is an excellent example of the versatility of parallelprocessing.

Investigation reveals several powerful techniques forimplementing table look-up. The choice depends mainly on the behavior ofthe search key and the table size and regularity. Among these techniquesare the following:Replicate the Table - 64 copies of table. Tolerable only if thetable is small.Repeat the Table Several Times and Route the Computation - I fthe table were repeated eight times, for example, the first sectionwould appear in PE's 0, 1, 2. 3, 4, 5, 6, and 7. The secondsection would appear in PE's 8 through 15; the third, in PE's 16through 23 and so forth to the last section, which would appearin PE's 56 through 63. The table look-up would now beperformed eight times, once for each section of the table.

Ateach performance the routine would recognize whether it was inthe proper section of the table in each PE. By the time the eightlook-ups were complete, 64 values would be obtained. Theactual number of repetitions for a particular problem depends onthe relative size of the table and the amount of computation timeavailable as a trade-off.Compute - Some tables can be replaced by computation. Whenthis is true, it is because, in a serial machine, the computationtakes longer than the table look-up.

In a parallel machine, thecomputation runs 64 times as fast, so that the trade-off mayfavor computation.Interpolate More Intelligently - Use of more complicatedinterpolation formulas results in fewer entries being needed in atable. This is a special case of substituting more computation forless table.Use Regularities of the lndependent Variable - Suppose a largetable is storing f(x), where x is the independent variable. Inmany problems, x will vary smoothly from one PE to thenext. We keep in any given PE, say PE number "p", only thatportion of the table that refers to values of f(x) for x near thevalue xp contained in that PE. As xp changes, we come to thecase that f(xp) is no longer contained in the portion of the tablein PE number p. Then we digress to a table rearranging routine,which, in general, will only have to move copies of values fromneighboring PEs.-7-PE NUMBERPEOVALUE OF X ( ATTHIS STAGEOF THECOMPUTATION)4.5PE1PE2P E ~ PE4PE5PE6PE7illustration of Table Stored Using Regularities of the lndependent VariableThe accompanying figure shows an example of such a tablehaving 100'items with only 25 items required to be stored in eachPE of the 8-PE example array.

Only as much of the table ascorresponds to the range of x is stored in irnmediately accessiblememory (84 of the items in the table of the example). When xgoes out of range of the irnmediately accessible table (above 84 inthe example), more table must be brought in (Perhaps, a copystored in array memory but in more compact form).SYSTEM ELEMENTSARRAY SUBSYSTEMcontrol and interrupt control. The FINST/PE instructions, which controlthe operation of the 64 pEts executing in parallel, may require somepreliminary operation to be performed by the ADVAST (e.g., operationssuch as address arithmetic or the obtaining of a literal to append to theinstruction).. .:,um-r .7The concept of the ILLIAC IV is the use of an array of separate andidentical Processing Units. This architecture leads to programmingflexibility that is not found in the competing architectures. For example,access time to memory is shorter and addressing memory is made flexibleby the existence of a separate address in each Processing Unit.

In additionthe replication leads to economy of design and manufacture...8When the instruction reaches ADVAST, it is decoded partially to determinewhich type it is, and ADVAST operations are performed on it asrequired. ADVAST has access to four accumulators, a 64-word localoperand store, and miscellaneous registers. If the instruction concerns theseregisters only, it is executed entirely a t ADVAST.

If the instruction callsfor PE operations, ADVAST may be required to do some preparation,Control Unit (CU)IThe Control Unit is the portion of the ILLIAC IV System that performsthe initial processing of instructions up to and including the generation ofdetailed instruction microsequences for a step-by-step control of theProcessing Elements (PE). All execution of instructions in the array iscontrolled by the instruction decoding stations in the CU.The flow of instructions through the CU isshown in the figure by the greenarrows that form a path vertically descending through the figure. Theinstruction stream enters the CU by being fetched from the array memory(PEM's) to the instruction memory that is local to the CU. Fetching is donein blocks of 16 instructions each.

Management of this instruction memoryis assigned to an autonomous section of the Control Unit called theInstruction Look Ahead (ILA). As the Advanced Station (ADVAST) isfinished with each instruction, the ILA sends the next instruction toADVAST for initial decoding. The ILA checks that the next instruction isin the instruction memory, and if it is not, the ILA fetches it and its wholeblock of 16 instructions. Since the ILA keeps track of the instructions interms of their memory addresses, its operation is completely transparent toall programmers.The instruction set has two general types of instructions: those usedprimarily to control the internal operations of the CU (ADVASTinstructions) and those used primarily to control Processing Unit (PU)operations (FINSTIPE instructions).

The instructions that specify the CUoperation (ADVAST instructions) are used for such functions as loopINSTRUCTIONLOOK-AHEADFROM A L L PEM'SINSTRUCTIONADVANCEDSTATIONMAINTENANCEI1F]INSTRUCTIONtolfromDESCRIPTORCONTROLLERCONTROLBUSDATA ANDADDRESS BUSControl UnitCONTROLBUSMODE STATUSFOR 64 PE'Sespecially in the address/literal field of the instruction. Instructions thathave been completed by ADVAST are then discarded. Those that areintended for execution by the array of PE's are passed to the FinalInstruction Queue (FINO) with the ADVAST-prepared address/literalfield. This revised instruction stream is now fed to the Final Station(FINST) which issues commands to {he PE's on the basis of the instructionsit receives.

The commands issued by the FlNST cause similar opera$m.gptake place simultaneously in all the PE's.ADVAST instructions affect nothing but ADVAST itself, and mostADVAST operations on other instructions are such that ADVAST andFlNST can operate most o f the time independently of opeanother. Consequently, the ADVAST operations can be carried on at thesame time as the executions of some previous instruction in the FlNST andPE's. The FlNQ is composed of eight instruction storage positions thatallow timesmoothing between ADVASTand FINST.

This overlap betweenADVAST and FlNST causes the Processing Elements to be keptcontinuously busy, as long as the number of ADVAST instructions is nottoo great in any given segment of code.An occasional instruction may rguire cooperation between ARVAST andFINST, or the PE's. These instructions will cause ADVAST to wait until allprevious instructions are completed, a t all stations, before their executioncan proceed.ADVAST executes those portions of the code which can be calledhousekeeping and has a number of facilities to aid it in this task.

One ofthese i s the local operand store which serves several functions. For example,it may contain index words that are designed primarily for the control ofloops of instructions; it may contain numerical variables that are to bebroadcast to the PE's in parallel; or it may contain "control vectors"(words containing one bit per PE) that are destined to be transmitted to thePE mode bits for on-off control of the PE's. These functions are notexplicit in the hardware, but the data in the local operand store is put toexplicit use only as a function of the program being executed inADVAST.

The machine language of ILLIAC IV provides a number ofinstructions for exercising this control. For example:LOAD -Transfer one word from array memory to the localoperand store.0TX- -M -Test index (greater, less or equal as specified bythe letters supplied for "- -"I against the limit contained withthe index word, and modify the index by adding the signedincrement also contained within the index word.0LDL -Transfer a word from the local operand store to one ofthe accumulators from which preparation of the addresslliteralfield of PE instructions takes place.LDE -Transfer each bit of the accumulator (assumed tocontain a control vector) to the mode bit of the correspondingPE.0SETC -Transfer the mode bit (a bit in the PE which turns iton and off) from each PE to the corresponding bit number ofthe accumulator.LEAD0 - Convert the leading ONE of the accumulator(assumed loaded by a SETC instruction) into its correspondingbit number (which is now the PE number of the successfulPE).The Memory Service Unit (MSU) resolves the conflicts of the three users ofarray memory: 110, FINST, and ILA.

It also transmits the appropriateaddress to memory and exercises control over the memory cycle.The Test Maintenance Unit (TMU) provides the control channel to the CUfrom the 6 6700 and the manual maintenance panel.Processing UnitA Processing Unit (PU) functions as a general-purpose computer under thedirection of the CU. All of the 64 PU's in the ILLIAC IV System areelectrically, mechanically, and functionally identical. Each PU consists of aProcessing Element (PE), a Memory Logic (MLU)., and a Processing ElementMemory (PEM). Data and control inputs from the PE and MLU are shownbelow.Tolfrom Other Processing ~ l e m i a % IIIPROCESSINGELEMENTMEMORYLOGICI+1Tolf romControl UnitELEMENTMEMORY(PEM),IIITdfrom110 SubsystemTo Control UnitProcessing Unit Data and Control PathsFor control, the PE and MLU receive enable signals from the CU for thesequential enabling of data paths and logic during instruction execution andfor controlling the reading and writing in the PEM.