EP0214718A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Digital computer
Assignee: Alliant Computer Systems Corp
•
Filing: 1986-06-17
•
Granted: —
•
Expires: 2006-06-17
Abstract
Abstract An efficient technique for concurrently executing the iterations of an iterative construct is described. A parallel-processing computer is provided which is capable of successfully processing computationally intensive applications typically found in engineering and scientific applications. A technique is also described for interleaving the memory elements of a parallel-processing computer, and in particular one adapted for use in processing computationally intensive applications involving memory accesses at fixed strides. The memory elements (for example, cache sections) are highly accessible to the processors. There is also described a backplane-resident switch for selectively connecting any selected plurality of first sub-system buses to any selected plurality of second sub-system buses.
Inventors
- 👤 Robert L. Fredieu
- 👤 Ronald H. Gruner
- 👤 Richard T. Mcandrew
- 👤 Craig J. Mundie
- 👤 Mathew J. Myszewski
- 👤 William K. Stewart
- 👤 James E. Veres
- 👤 Michael L. Ziegler
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 05:40
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/45; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0844; G06F12/0846; G06F12/0851; G06F12/0806; G06F12/084; G06F12/10; G06F12/1027; G06F12/1036; G06F12/1045; G06F12/1054; G06F12/109; G06F13/00; G06F13/14; G06F13/16; G06F13/1605; G06F13/1652; G06F13/1657; G06F13/38; G06F13/40; G06F13/4004; G06F13/4022; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4482; G06F9/4484; G06F9/4486
Claims Analysis
Total Claims: 113
Claim 1
Independent Claim
95 words
A digital computer for processing a program containing an iterative construct, said digital computer comprising a plurality of processors, each said processor adapted for serially processing, without the assistance of the other said processors, those portions of said program outside of said iterative construct and each paid processor adapted for concurrently processing different iterations of said iterative construct, means for activating those of said processors that have been idle at the start of said iterative construct and for transferring sufficient state information to the activated processors so that they can begin concurrent processing of iterations.
Claim 2
Dependent Claim
95 words
A digital computer for processing a program containing an iterative construct, said digital computer comprising a plurality of processors, each said processor adapted for serially processing, without the assistance of the other said processors, those portions of said program outside of said iterative construct and each paid processor adapted for concurrently processing different iterations of said iterative construct, means for activating those of said processors that have been idle at the start of said iterative construct and for transferring sufficient state information to the activated processors so that they can begin concurrent processing of iterations.
Claim 3
Dependent Claim
143 words
The digital computer of claim 1 wherein said iterative construct contains one or more dependencies (a dependency comprising a first instruction that cannot properly be executed in a given iteration until a second instruction (which could be the same instruction as said first instruction) has been executed in a prior iteration), and wherein said digital computer further comprises waiting means for causing a said processor to delay further processing upon encountering said first instruction until it.receives a go-ahead signal indicating that said second instruction has been executed in said prior iteration, synchronizing means for storing information representative of the lowest iteration to have executed said second instruction, and far providing said go-ahead signal to said waiting means based on a comparison of said lowest iteration and said prior iteration, advancing means for informing said synchronizing means that said second instruction has been executed.
Claim 4
Dependent Claim
47 words
The digital computer of claim 2 wherein said advancing means includes means for sending said synchronizing means an advance-register signal when said second instruction has been executed, and said synchronizing means comprises a synchronization register and means for incrementing said register when an advance-register signal is received.
Claim 5
Dependent Claim
58 words
The digital computer of claim 3 wherein said advancing means includes its own waiting means for causing a processor that has executed said second instruction to delay further processing and to delay issuing said advance-register signal until it is informed that all lower iterations than the one it is executing have caused said synchronization register to be incremented.
Claim 6
Dependent Claim
36 words
The digital computer of claim 4 wherein said waiting means comprises means for effecting said delay of further processing in response to recognition of an await instruction (e.g., the CAWAIT instruction) appearing before said first instruction.
Claim 7
Dependent Claim
38 words
The digital computer of claim 5 wherein said advancing means comprises means for initiating the action performed by said advancing means in response to recognition of an advance instruction (e.g., the CADVANCE instruction) appearing after said second instruction.
Claim 8
Dependent Claim
30 words
The digital computer of claim 3 wherein said synchronization means comprises a plurality of synchronization registers, each said register being capable of synchronizing a different dependency in said iterative construct.
Claim 9
Dependent Claim
81 words
The digital computer of claim 6 wherein said synchronization means comprises a plurality of said synchronization registers, each said register being capable of synchronizing a different dependency in said iterative construct said await instruction provides said waiting means with an argument specifying from which of said plural synchronization registers said go-ahead signal must come from, and said advance instruction provides said advancing means with an argument specifying which of said plural synchronization registers is to be incremented by said advance-register signal.
Claim 10
Dependent Claim
34 words
The digital computer of claim 3 or 8 wherein said synchronization means further comprises comparison means for comparing the contents of a said synchronization register to the current iteration being executed by a processor.
Claim 11
Dependent Claim
48 words
The digital computer of claim 9 wherein each said processor further comprises a current iteration register containing a number representative of the current iteration the processor is processing and wherein said comparison means compares the contents of a synchronization register to the contents of said current iteration register.
Claim 12
Dependent Claim
73 words
The digital computer of claim 9 wherein the offset between said given iteration (the iteration in which the first instruction is executed) and said prior iteration (the iteration in which said second instruction must have been executed in order for said first instruction to be executed) is provided as an argument in said await instruction and said comparison means compares the contents of a synchronization register to the current iteration minus said offset.
Claim 13
Dependent Claim
47 words
The digital computer of claim 3 or 8 wherein each said synchronization register contains only the least significant bits of said lowest iteration and the number of said least significant bits is selected to be sufficient to express the maximum difference in iteration number being concurrently processed.
Claim 14
Dependent Claim
86 words
The digital computer of claim 12 wherein said advancing means includes its own waiting means for causing a processor that has executed said second instruction to delay further processing and to delay issuing said advance-register instruction until it is informed that all lower iterations than the one it is executing have caused said synchronization register to be incremented, and said synchronization registers are selected to be sufficient to express the number N-l, where N is the maximum number of said processors concurrently processing said iterative construct.
Claim 15
Dependent Claim
42 words
The digital computer of claim 12 wherein said synchronization register contains a further bit (the PAST bit) and means are provided for asserting - said PAST bit locally in a said processor when said register has been incremented in a given iteration.
Claim 16
Dependent Claim
19 words
The digital computer of claim 2 wherein said processors include means for processing vector instructions within said iterative construct.
Claim 17
Dependent Claim
61 words
The digital computer of claim 1 wherein said digital computer further comprises means for transferring further state information to said activated processors so that any one of them can take up serial processing at the conclusion of concurrent processing of said iterative construct, and means for assigning any one of said processors to serial processing at the conclusion of concurrent processing.
Claim 18
Dependent Claim
30 words
The digital computer of claim 16 wherein the processor assigned serial processing at the conclusion of said construct is the processor that has executed the final iteration of said construct.
Claim 19
Dependent Claim
23 words
The digital computer of claim 16 wherein said further state information comprises the value of the stack pointer just before concurrent processing began.
Claim 20
Dependent Claim
18 words
The digital computer of claim 16 wherein said sufficient state information comprises the value of the program counter.
Claim 21
Dependent Claim
27 words
The digital computer of claim 19 wherein said sufficient state information further comprises the value of the frame pointer and the maximum iteration of said iterative construct.
Claim 22
Dependent Claim
52 words
The digital computer of claim 1 wherein said digital computer further comprises iteration-assignment means for assigning iterations to said processors by assigning the next iteration (i.e., the highest numbered iteration not yet assigned) to the first processor to.request an iteration (or to one of the processors to simultaneously first request an iteration).
Claim 23
Dependent Claim
48 words
The digital computer of claim 21 wherein said iteration-assignment means comprises means in each processor for bidding for a new iteration, means for determining the number N of processors simultaneously bidding for an iteration, and means for assigning the next N iterations to the N processors simultaneously bidding.
Claim 24
Dependent Claim
21 words
The digital computer of claim 22 wherein said means for determining and said means for assigning reside in each said processor.
Claim 25
Dependent Claim
73 words
The digital computer of claim 23 wherein said means for determining the number of processors simultaneously bidding comprises a plurality of ready lines extending on a bus running between said processors, one line assigned to each said processor, means at each processor for asserting that processor's assigned ready line when the processor needs a new iteration, and means at each processor for determining the total number of said ready lines being concurrently asserted.
Claim 26
Dependent Claim
96 words
The digital computer of claim 24 wherein said means for assigning the next N iterations comprises a current-iteration register at each processor for storing the current iteration being processed by that processor, an iterations-already-assigned register at each processor for storing a number representative of the highest iteration already assigned or the next iteration to be assigned, incrementing means at each processor for incrementing said iterations-already-assigned register by the total number of ready lines asserted during any machine cycle, and means at each processor for determining the current iteration to be stored in said current iteration register.
Claim 27
Dependent Claim
25 words
The digital computer of claim 25 wherein said iterations-already-assigned register contains the next iteration to be assigned, i.e., the next iteration following those already assigned.
Claim 28
Dependent Claim
55 words
The digital computer of claim 25 wherein said means for determining the current iteration comprises means for determining the number of said ready lines being asserted by processors of lower rank than said processor making the determination, and means for adding said number of asserted lower-rank ready lines to the contents of said iterations-already-assigned register.
Claim 29
Dependent Claim
87 words
The digital computer of claim 23 or 25 wherein said means for activating and transferring state information transfers to all said processors the maximum iteration for which said iterative construct is to be executed, . each said processor further comprises a register for storing said maximum iteration and a comparator for comparing the said current iteration to said maximum iteration, and each said processor further comprises means for terminating concurrent processing when the output of said comparator indicates that said maximum iteration has been reached or exceeded.
Claim 30
Dependent Claim
56 words
The digital computer of claim 23 or 25 wherein said means for bidding, means for determining, and means for assigning residing in each processor are adapted to perform the next iteration assignment independently of other processors, based on the number of processors simultaneously bidding for an iteration and a predetermined rank number assigned to each processor.
Claim 31
Dependent Claim
35 words
The digital computer of claim 23 or 25 wherein each said processor bidding for an iteration assigns an iteration to itself at the same time as any other processors then bidding assign iterations to themselves.
Claim 32
Dependent Claim
46 words
The digital computer of claim 22 or 25 wherein said iteration-assignment means assigns initial iterations using said means for bidding, means for determining, and means for assigning, and wherein each said processor is adapted to bid simultaneously for an initial iteration during initiation of concurrent processing.
Claim 33
Dependent Claim
130 words
The digital computer of claim 1 wherein said iterative construot contains one or more dependencies (a dependency comprising a first instruction that cannot properly be executed in a given iteration until a second instruction (which could be the same instruction as said first instruction) has been executed in a prior iteration), and wherein said digital computer further comprises concurrency control lines connecting said processors for passing concurrency control signals between said processors, and local concurrency control means at each said processor for transmitting and receiving said control signals from other processors and for controlling concurrent processing of said processor, said controlling including assigning iterations to said processor and causing said processor to delay further processing when necessary to synchronize dependencies, whereby control of said processors during concurrent processing is decentralized.
Claim 34
Dependent Claim
35 words
The digital computer of claim 32 wherein said concurrency control lines include a data bus for transferring state information such as the stack pointer between processors at the start of concurrent execution of said construct.
Claim 35
Dependent Claim
98 words
The digital computer of claim 33 wherein said concurrency control lines include a ready line for each processor for asserting that a processor needs to be assigned an iteration, one or more dependency-control lines for use by a processor to inform other processors that said second instruction has been executed in said prior iteration and that said first instruction may, therefore, be executed, one or more lines for -informing the processors of the initiation and conclusion of concurrent processing, and one or more data-control lines for tagging and controlling the flow of state information across said data bus.
Claim 36
Dependent Claim
39 words
The digital computer of claim 34 wherein said concurrency control means comprises an iterations-already-assigned register and one or more dependency-synchronization registers and wherein means are provided for assuring that said registers have the same contents in all said processors.
Claim 37
Dependent Claim
53 words
The digital computer of claim 1 wherein said iterative construct contains within it a conditional branch terminating processing of said iterative construct, and wherein said digital computer further comprises means for informing other said processors that said conditional branch has been taken and for causing said other processors to assume the idle state.
Claim 38
Dependent Claim
64 words
The digital computer of claim 36 further comprising means for preventing a said processor encountering a trap during concurrent execution of a given iteration of said construct from taking the trap until that said processor receives an indication (the "OK-to-trap" indication) that said given iteration is the lowest iteration being processed in which it is still possible for said conditional branch to be taken.
Claim 39
Dependent Claim
52 words
The digital computer of claim 37 wherein a said means for preventing the taking of a trap is provided at each said processor and means are provided for transmitting between processors information representative of said lowest iteration being processed in which it is still possible for said conditional branch to be taken.
Claim 40
Dependent Claim
85 words
The digital computer of claim 38 further comprising a trap-control register at each said processor for providing said indication, register advance means at each said processor for incrementing said trap-control register at the completion of an iteration (or at a point beyond which there is any possibility of said conditional branch occurring before completion of an iteration), and means for comparing the contents of said trap-control register to the current iteration being executed by that processor to determine when said OK-to-trap indication should be given.
Claim 41
Dependent Claim
59 words
The digital computer of claim 36 wherein means are provided at each processor for preventing a said processor from taking said branch during concurrent execution of a given iteration until that said processor receives an indication that said given iteration is the lowest iteration being processed in which it is still possible for said conditional branch to be taken.
Claim 42
Dependent Claim
111 words
The digital computer of claim 40 wherein there is provided a synchronization register for providing said indication that said given iteration is the lowest iteration, said means for preventing said branch comprise means for causing said processor to delay further processing in response to recognition of an await-quit instruction (or instructions) appearing before said conditional branch, said processing being delayed until said synchronization register reaches a value equal to the current iteratipn, and means are provided at each said processor for incrementing said register at the completion of each said iteration (or at a point beyond which there is any possibility of said conditional branch occurring before completion of an iteration).
Claim 43
Dependent Claim
41 words
The digital computer of claim 1 wherein said digital computer further comprises means for providing each said processor with a private stack for use during concurrent processing for storage of data unique to an iteration (e.g., temporary variables and subroutine arguments).
Claim 44
Dependent Claim
59 words
The digital computer of claim 42 wherein means are provided for saving the contents of the stack pointer register in use prior to concurrent processing, for loading a pointer for said private stack into said register at the start of concurrent processing, and for restoring the stack pointer register with the saved value at the completion of concurrent processing.
Claim 45
Dependent Claim
45 words
The digital computer of claim 43 wherein means are provided for saving a copy in each processor of the stack pointer in use prior to concurrent processing so that a said copy will be available to whichever processor is the one to resume serial processing.
Claim 46
Dependent Claim
100 words
The digital computer of claim 1 wherein said program contains a second iterative construct (said first-mentioned construct being hereinafter referred to as said. first iterative construct), and wherein said second iterative construct is either within or outside of said first iterative construct, and wherein said digital computer further comprises means for detecting during execution whether said second iterative construct is within said first construct, and for causing the processor starting said second iterative construct to execute it serially (all iterations on the same processor) if it is within said first construct and concurrently if it is outside said first construct.
Claim 47
Dependent Claim
32 words
The digital computer of claim 45 wherein means are provided for saving the current iteration of said first construct when said second construct is encountered within said first construct and executed serially.
Claim 48
Dependent Claim
33 words
The digital computer of claim 46 wherein means are provided for also saving the maximum iteration of said first construct when said second construct is encountered within said first construct and executed serially.
Claim 49
Dependent Claim
38 words
The digital computer of claim 47 wherein a status bit (or bits) is provided for indicating whether the iterative construct being processed is within another iterative construct being executed concurrently (i.e., whether the construct being processed is nested).
Claim 50
Dependent Claim
38 words
The digital computer of claim 48 wherein means are provided for saving the content of said status bit at the start of execution of a nested construct and for restoring the saved value at completion of the construct.
Claim 51
Dependent Claim
65 words
The digital computer of claim 45 wherein said means for detecting whether said second iterative construct is within said first iterative construct includes means for detecting whether a third and subsequent iterative constructs are within said first construct, either because they are called directly by said first construct or because they are called by said second construct or subsequent constructs nested within said first construct.
Claim 52
Dependent Claim
139 words
A digital computer for processing a program containing one or more vector instructions for operating on vectors each of N elements, said digital computer comprising a plurality of processors, each said processor being adapted for serially processing, without the assistance of the other said processors, portions of said program before and after said vector instructions, each said processor including means for concurrently processing a subset of said N elements using said vector instructions, means for dividing said N vector elements among said processors during execution of said program based on the number of processors participating in concurrent processing, and means for activating those of said processors that have been idle at the start of said vector instructions and for transferring sufficient state information to the activated processors so that they can begin concurrent processing of their assigned vector elements.
Claim 53
Dependent Claim
139 words
A digital computer for processing a program containing one or more vector instructions for operating on vectors each of N elements, said digital computer comprising a plurality of processors, each said processor being adapted for serially processing, without the assistance of the other said processors, portions of said program before and after said vector instructions, each said processor including means for concurrently processing a subset of said N elements using said vector instructions, means for dividing said N vector elements among said processors during execution of said program based on the number of processors participating in concurrent processing, and means for activating those of said processors that have been idle at the start of said vector instructions and for transferring sufficient state information to the activated processors so that they can begin concurrent processing of their assigned vector elements.
Claim 54
Dependent Claim
49 words
The digital computer of claim 51 wherein the number of said processors participating in concurrent processing is variable and not predetermined and wherein said means for dividing said N vector elements among said processors includes means for determining the number of processors participating at the start of concurrent processing.
Claim 55
Dependent Claim
25 words
The digital computer of claim 52 further comprising means for instructing said processors whether the vector is to be divided horizontally or vertically between processors.
Claim 56
Dependent Claim
34 words
The digital computer of claim 53 further comprising means at each processor for determining during processing said length, offset, and increment to be used by said processor in making said division of said vector.
Claim 57
Dependent Claim
55 words
The digital computer of claim 51 wherein said processors are adapted to initiate concurrent processing of said vector upon recognition of a start-vector-concurrency instruction placed before the first of said vector instructions, and said processors are adapted to terminate vector processing of said vector upon recognition of a repeat instruction placed after said vector instructions.
Claim 58
Dependent Claim
48 words
The digital computer of claim 52 wherein each said processor includes logic circuitry for concurrently processing different iterations of an iterative construct, and wherein said logic circuitry also serves as said means for concurrently processing a subset of said N elements and said means for activating idle processors.
Claim 59
Dependent Claim
74 words
The digital computer of claim 54 wherein said means for determining said length, offset, and increment includes, for horizontal division of the vector, means for determining said length according to the expression: where N is the total number of vector elements, V PN is the virtual processor number, NUM is the highest virtual processor number, and CEIL means that the result is rounded up to the next highest integer if not already an integer.
Claim 60
Dependent Claim
48 words
The digital computer of claim 54 wherein said means for determining said length, offset, and increment includes, for horizontal division of the vector, means for determining said offset according to the expression: where VINCR is the increment of the original vector and VPN is the virtual processor number.
Claim 61
Dependent Claim
49 words
The digital computer of claim 54 wherein said means for determining said length, offset, and increment includes, for horizontal division of the vector, means for determining said increment acording to the expression: where VINCR is the increment of the original vector and NUM is the highest virtual processor number.
Claim 62
Dependent Claim
84 words
The digital computer of claim 54 wherein said means for determining said length, offset, and increment-includes, for vertical division of the vector, means for determining said length acording to the expression: where N is the total number of vector elements, VP N is the virtual processor number, NUM is the highest virtual processor number, CEIL means that the result is rounded up to the next highest integer if not already an integer, and MIN is the minimum of the two parameters within the brackets.
Claim 63
Dependent Claim
73 words
The digital computer of claim 54 wherein said means for determining said length, offset, and increment includes, for vertical division of the vector, means for determining said offset acording to the expression: where N is the total number of vector elements, VPN is the virtual processor number, NUM is the highest virtual processor number, and CEIL means that the result is rounded up to the next highest integer if not already an integer.
Claim 64
Dependent Claim
149 words
A digital computer comprising a plurality of memory elements, said memory elements being interleaved (i.e., each is assigned memory addresses on the basis of a low order portion of the memory address), a plurality of parallel processors, said processors each having means for initiating an access of data from any of said memory elements simultaneously with accesses of other said processors, said memory elements each being capable of accepting an access from just one of said processors during a given cycle, wherein said memory elements are so interleaved that the access pattern generated by said processors when accessing data at a predetermined stride permits all of said processors to reach a phase relationship with other said processors in which each said processor is able to access a different said memory element simultaneously without creating access conflicts (i.e., more than one processor simultaneously attempting to access the same memory element).
Claim 65
Dependent Claim
149 words
A digital computer comprising a plurality of memory elements, said memory elements being interleaved (i.e., each is assigned memory addresses on the basis of a low order portion of the memory address), a plurality of parallel processors, said processors each having means for initiating an access of data from any of said memory elements simultaneously with accesses of other said processors, said memory elements each being capable of accepting an access from just one of said processors during a given cycle, wherein said memory elements are so interleaved that the access pattern generated by said processors when accessing data at a predetermined stride permits all of said processors to reach a phase relationship with other said processors in which each said processor is able to access a different said memory element simultaneously without creating access conflicts (i.e., more than one processor simultaneously attempting to access the same memory element).
Claim 66
Dependent Claim
78 words
The digital computer of claim 62 wherein said memories are so interleaved that the access pattern generated by said processors for a given power-of-two stride greater than one meets the condition that the pattern tolerates being offset with respect to an identical pattern by an OFFSET or any multiple of said OFFSET, said OFFSET being equal to the length of the access pattern divided by the number of memory elements (wherein tolerating means that no access conflicts arise).
Claim 67
Dependent Claim
75 words
The digital computer of claim 63 wherein said memories are so interleaved that the access pattern generated by said processors for said given- stride meets the further condition that the pattern includes at least one conflict at every offset other than said OFFSET and multiples of said OFFSET, whereby said conflicts force said processors to assume a phase relationship with each other wherein the offset between access patterns equals said OFFSET or a multiple thereof.
Claim 68
Dependent Claim
42 words
The digital computer of claim 64 wherein there are four said memory elements W,X,Y,Z and said memory elements are interleaved so that at a stride of one the access pattern is WXXWYZZY and at a stride of two the pattern is WXYZ.
Claim 69
Dependent Claim
42 words
The digital computer of claim 64 wherein there are four said memory elements W,X,Y,Z and said memory elements are interleaved so that at a stride of one the access pattern is WXXWYYZZ and at a stride of two the pattern is WXYZ.
Claim 70
Dependent Claim
42 words
The digital computer of claim 64 wherein there are four said memory elements W,X,Y,Z and said memory elements are interleaved so that at a stride of one the access pattern is WWXZYXZY and at a stride of two the pattern is WXYZ.
Claim 71
Dependent Claim
51 words
The digital computer of claim 64 wherein there are four said memory elements W,X,Y,Z and said memory elements are interleaved so that at a stride of one the access pattern is WWXXXXWWYYZZZZYY, at a stride of two the pattern is WWXZYXZY, and at a stride of four the pattern is WXYZ.
Claim 72
Dependent Claim
41 words
The digital computer of claim 64 wherein there are eight said memory elements A,B,C,D,E,F,G,H and said memory elements are interleaved so that at a stride of one the access pattern is ABCDDCBAEFGHHGFE, at a stride of two the pattern is ACDBEGHF.
Claim 73
Dependent Claim
14 words
The digital computer of claim 65 wherein said memory elements are interleaved as follows:
Claim 74
Dependent Claim
32 words
The digital computer of claim 70 wherein said three address bits on which said interleaving is done are bits five through three of the byte-level address for data in said memory elements.
Claim 75
Dependent Claim
35 words
The digital computer of claim 62, 64, 65, 70, or 71 wherein said memory elements are sections of a cache and said digital computer further comprises a main memory to which said cache is connected.
Claim 76
Dependent Claim
30 words
The digital computer of claim 72 wherein said memory elements each include means for choosing among processors simultaneously contending for access on the basis of a fixed processor priority ranking.
Claim 77
Dependent Claim
33 words
The digital computer of claim 62, 64, 65, 70, or 71 wherein said processors include means for concurrently processing the same instructions and data, wherein said data is accessed from said memory elements.
Claim 78
Dependent Claim
30 words
The digital computer of claim 74 wherein said memory elements each include means for choosing among processors simultaneously contending for access on the basis of a fixed processor priority ranking.
Claim 79
Dependent Claim
21 words
The digital computer of claim 74 wherein said processors include means for concurrently processing different iterations of the same iterative construct.
Claim 80
Dependent Claim
30 words
The digital computer of claim 76 wherein said memory elements are sections of a cache and said digital computer further comprises a main memory to which said cache is connected.
Claim 81
Dependent Claim
30 words
The digital computer of claim 77 wherein said memory elements each include means for choosing among processors simultaneously contending for access on the basis of a fixed processor priority ranking.
Claim 82
Dependent Claim
52 words
A digital computer comprising a main memory for storing data, a cache for storing copies of said data, said cache being connected to said main memory, a plurality of parallel processors connected to said cache, and means for permitting each of said processors to access the same memory locations of said cache.
Claim 83
Dependent Claim
52 words
A digital computer comprising a main memory for storing data, a cache for storing copies of said data, said cache being connected to said main memory, a plurality of parallel processors connected to said cache, and means for permitting each of said processors to access the same memory locations of said cache.
Claim 84
Dependent Claim
30 words
The digital computer of claim 79 wherein said processors include means for concurrently processing the same instructions and data, wherein said data is read from and written to said cache.
Claim 85
Dependent Claim
21 words
The digital computer of claim 80 wherein said processors include, means for concurrently processing different iterations of the same iterative construct.
Claim 86
Dependent Claim
50 words
The digital computer of claim 79 wherein said cache comprises a plurality of cache sections, each said processor has means for accessing the same memory locations of each said cache section, and means are provided for a plurality of said processors to simultaneously access a plurality of said cache sections.
Claim 87
Dependent Claim
32 words
The digital computer of claim 82 wherein said cache sections are interleaved (i.e., each cache section is assigned memory addresses on the basis of a low order portion of the memory address).
Claim 88
Dependent Claim
31 words
The digital computer of claim 83 wherein said cache sections include means for accessing blocks of data from said main memory and means for dividing each said block between cache sections.
Claim 89
Dependent Claim
60 words
The digital computer of claim 84 wherein two or more of said cache sections each include means for driving a common memory address bus with the block address of the block of data to be accessed in memory, and said two or more cache sections each include means for concurrently reading said block address from said common memory address bus.
Claim 90
Dependent Claim
66 words
The digital computer of claim 85 further comprising . two or more main memory data buses, one said data bus connected to each of said two or more cache sections, and means in said main memory for transferring across any one said data bus only those portions of said data block with addresses assigning them to the cache section to which said data bus is connected.
Claim 91
Dependent Claim
44 words
The digital computer of claim 86 wherein there are four said cache sections, said interleaving is said blocks are defined by the highest bit of the address bits used to define said interleaving, and said blocks are divided between pairs of said cache sections.
Claim 92
Dependent Claim
31 words
The digital computer of claim 87 wherein said three address bits on which interleaving is based are the fifth through the third bits of the byte-level address in said cache sections.
Claim 93
Dependent Claim
17 words
The digital computer of claim 87 wherein said pairs of cache sections share a common circuit board.
Claim 94
Dependent Claim
30 words
The digital computer of claim 87 wherein said memory elements each include means for choosing among processors simultaneously contending for access on the basis of a fixed processor priority ranking.
Claim 95
Dependent Claim
89 words
A digital computer comprising a plurality of first subsystems resident on one or more first circuit boards, each said first subsystem having a first subsystem bus, a plurality of second subsystems resident on one or more second circuit boards, each said second subsystem having a second subsystem bus, a backplane circuit board to which said first and second circuit boards are connected, a bus-switching means resident on said backplane circuit board for selectively connecting any selected plurality of first subsystem buses to any selected plurality of second subsystem buses.
Claim 96
Dependent Claim
89 words
A digital computer comprising a plurality of first subsystems resident on one or more first circuit boards, each said first subsystem having a first subsystem bus, a plurality of second subsystems resident on one or more second circuit boards, each said second subsystem having a second subsystem bus, a backplane circuit board to which said first and second circuit boards are connected, a bus-switching means resident on said backplane circuit board for selectively connecting any selected plurality of first subsystem buses to any selected plurality of second subsystem buses.
Claim 97
Dependent Claim
12 words
The digital computer of claim 91 wherein said first subsystems are processors.
Claim 98
Dependent Claim
31 words
The digital computer of claim 92 wherein said second subsystems are memories, and wherein said bus-switching means is adapted to permit any said processor to access any address in said memories.
Claim 99
Dependent Claim
11 words
The digital computer of claim 93 wherein said memories are caches.
Claim 100
Dependent Claim
15 words
The digital computer of claim 94 wherein said caches are sections of a global cache.
Claim 101
Dependent Claim
19 words
The digital computer of claim 95 wherein there are a greater number of said processors than said cache sections.
Claim 102
Dependent Claim
30 words
The digital computer of claim 96 wherein said cache sections are adapted to accept accesses from said processors more frequently than an individual said processor is adapted to make accesses.
Claim 103
Dependent Claim
77 words
The digital computer of claim 97 further comprising processor-access control lines separate from said bus-switching means, means in said processors for asserting said access lines to initiate an access and to indicate which of said cache sections the processor desires to access, cache-acknowledge control lines separate from said bus-switching means, and means in said cache sections for asserting said acknowledge lines to inform contending processors whether they have won access to said cache section via said switch.
Claim 104
Dependent Claim
20 words
The digital computer of claim 98 wherein the means for controlling said bus-switching means resides exclusively in said cache sections.
Claim 105
Dependent Claim
56 words
The digital computer of claim 99 further comprising cache-not-ready control lines separate from said bus-switching means, and means in each cache section for asserting a not-ready line to inform a processor after it has gained access to a cache section that it must wait before the data transfer between it and the cache section may proceed.
Claim 106
Dependent Claim
12 words
The digital computer of claim 95 wherein said cache sections are interleaved.
Claim 107
Dependent Claim
32 words
The digital computer of claim 93, 95, or 101 wherein said processors include means for concurrently processing the same instructions and data, and said data resides in said memories or cache sections.
Claim 108
Dependent Claim
21 words
The digital computer of claim 102 wherein said processors include means for concurrently processing different iterations of the same iterative construct.
Claim 109
Dependent Claim
70 words
A digital computer comprising a plurality of parallel processors, each said processor having one or more processor buses, a plurality of memories, each said memory having one or more memory buses, a bus-switching means for selectively connecting any selected plurality of processor buses to any selected plurality of memory buses, wherein said processors include means for concurrently processing the same instructions and data, and said data resides in said memories.
Claim 110
Dependent Claim
70 words
A digital computer comprising a plurality of parallel processors, each said processor having one or more processor buses, a plurality of memories, each said memory having one or more memory buses, a bus-switching means for selectively connecting any selected plurality of processor buses to any selected plurality of memory buses, wherein said processors include means for concurrently processing the same instructions and data, and said data resides in said memories.
Claim 111
Dependent Claim
21 words
The digital computer of claim 104 wherein said processors include means for concurrently processing different iterations of the same iterative construct.
Claim 112
Dependent Claim
22 words
The digital computer of claim 91 wherein said bus-switching means comprises a plurality of gate arrays mounted on said backplane circuit board.
Claim 113
Dependent Claim
22 words
The digital computer of claim 104 wherein said bus-switching means comprises a plurality of gate arrays mounted on a backplane circuit board.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.