US4783736A — Digital computer with multisection cache

Claim 1

Independent Claim 223 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 processors connected in parallel, said processors each having means for intiating 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, said memory elements being interleaved and said interleaving being characterized by access patterns generated by said processors when accessing data at particular strides, said interleaving being selected so that the access patterns generated at a stride of one and a stride of two each meet the conditions that (1) the pattern will tolerate being offset with respect to an identical pattern by a particular OFFSET and any multiple of said OFFSET (wherein tolerating means that no memory access conflicts arise, i.e., more than one processor simultaneously attempting to access the same memory element) and (2) the pattern includes sufficient conflicts at offsets other than said particular OFFSET to force said processors to assume a relationship wherein said particular OFFSET is achieved, so that each said processor is able to access a different said memory element simultaneously without creating access conflicts.

Claim 2

Dependent Claim 223 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 processors connected in parallel, said processors each having means for intiating 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, said memory elements being interleaved and said interleaving being characterized by access patterns generated by said processors when accessing data at particular strides, said interleaving being selected so that the access patterns generated at a stride of one and a stride of two each meet the conditions that (1) the pattern will tolerate being offset with respect to an identical pattern by a particular OFFSET and any multiple of said OFFSET (wherein tolerating means that no memory access conflicts arise, i.e., more than one processor simultaneously attempting to access the same memory element) and (2) the pattern includes sufficient conflicts at offsets other than said particular OFFSET to force said processors to assume a relationship wherein said particular OFFSET is achieved, so that each said processor is able to access a different said memory element simultaneously without creating access conflicts.

Claim 3

Dependent Claim 42 words

The digital computer of claim 1 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 4

Dependent Claim 42 words

The digital computer of claim 1 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 5

Dependent Claim 42 words

The digital computer of claim 1 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 6

Dependent Claim 51 words

The digital computer of claim 1 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 7

Dependent Claim 41 words

The digital computer of claim 1 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 8

Dependent Claim 15 words

The digital computer of claim 1 wherein there are at least four said memory elements.

Claim 9

Dependent Claim 27 words

The digital computer of claim 7 wherein said particular OFFSET is equal to the length of said access pattern divided by the number of said memory elements.

Claim 10

Dependent Claim 32 words

The digital computer of claim 1 or 2 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 11

Dependent Claim 30 words

The digital computer of claim 9 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 12

Dependent Claim 30 words

The digital computer of claim 1 or 2 wherein said processors include means for concurrently processing the same instructions and data, wherein said data is accessed from said memory elements.

Claim 13

Dependent Claim 30 words

The digital computer of claim 11 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 14

Dependent Claim 21 words

The digital computer of claim 11 wherein said processors include means for concurrently processing different iterations of the same iterative construct.

Claim 15

Dependent Claim 30 words

The digital computer of claim 13 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 16

Dependent Claim 30 words

The digital computer of claim 14 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 17

Dependent Claim 124 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, said cache comprising a plurality of cache sections, each said processor having means for accessing the same memory locations of each said cache section, means for a plurality of said processors to simultaneously access a plurality of said cache sections, 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), 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 18

Dependent Claim 124 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, said cache comprising a plurality of cache sections, each said processor having means for accessing the same memory locations of each said cache section, means for a plurality of said processors to simultaneously access a plurality of said cache sections, 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), 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 19

Dependent Claim 60 words

The digital computer of claim 16 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 20

Dependent Claim 65 words

The digital computer of claim 17 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 21

Dependent Claim 70 words

The digital computer of claim 18 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, 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 22

Dependent Claim 31 words

The digital computer of claim 19 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 23

Dependent Claim 29 words

The digital computer of claim 19 wherein said pairs of cache sections share a common circuit board and each of said circuit boards are identical, thereby enhancing implementational simplicity.

Claim 24

Dependent Claim 30 words

The digital computer of claim 19 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 25

Dependent Claim 74 words

A digital computer comprising a main memory for storing data, a cache for storing copies of said data, said cache connected to said main memory, a plurality of parallel processors connected to said cache, means for permitting each of said processors to access the same memory locations of said cache, 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 26

Dependent Claim 74 words

A digital computer comprising a main memory for storing data, a cache for storing copies of said data, said cache connected to said main memory, a plurality of parallel processors connected to said cache, means for permitting each of said processors to access the same memory locations of said cache, 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 27

Dependent Claim 21 words

The digital computer of claim 23 wherein said processors include means for concurrently processing different iterations of the same iterative construct.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1991-11-08	1992-05-09	1992-11-08	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1995-11-08	1996-05-09	1996-11-08	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1999-11-08	2000-05-09	2000-11-08	$7700.00	Window Closed / Lapsed

Digital computer with multisection cache

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag