US5410689A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for merge sorting that assigns an optical memory capacity to concurrent sort cells
Assignee: Toshiba Corp
•
Filing: 1992-06-12
•
Granted: 1995-04-25
•
Expires: 2012-06-12
Abstract
Abstract According to this invention, an address converter for defining a start address of an external memory for each of sort controllers is arranged to each of sort cells or is commonly arranged to the sort cells. An optimal memory capacity for each of the sort controllers is assigned to the external memory. The plurality of sort controllers commonly use one memory bus, and use timings of the common memory bus are sequentially controlled between the plurality of sort controllers. The external memory can be commonly used as a buffer memory, and use efficiency of the memory can be increased. In addition, since the single memory bus is used, the number of input/output pins for the memory bus is decreased, and the plurality of sort controllers can be integrated on one chip without increasing the number of input/output pins.
Inventors
- 👤 Kazuo Togo
- 👤 Masahiro Hiruma
- 👤 Susuma Matsuda
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 14:57
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/36; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
177 words
A sort processing apparatus in which 2 n data can be simultaneously processed comprising: a plurality of sort cells, connected in series, for performing a merge sort on two sets of input data, wherein each of said sort cells includes: a buffer memory for temporarily storing said two sets of input data; a sort executing unit for executing a sort on said two sets of data stored in said buffer memory; and a memory bus for connecting said sort executing unit to said buffer memory; an external memory, having an address space, connected to each of said sort cells; and address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, and wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, an mth sort cell includes addresses ##EQU1## n is equal to a total number of said sort cells, and m=1 to n-1.
Claim 2
Dependent Claim
177 words
A sort processing apparatus in which 2 n data can be simultaneously processed comprising: a plurality of sort cells, connected in series, for performing a merge sort on two sets of input data, wherein each of said sort cells includes: a buffer memory for temporarily storing said two sets of input data; a sort executing unit for executing a sort on said two sets of data stored in said buffer memory; and a memory bus for connecting said sort executing unit to said buffer memory; an external memory, having an address space, connected to each of said sort cells; and address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, and wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, an mth sort cell includes addresses ##EQU1## n is equal to a total number of said sort cells, and m=1 to n-1.
Claim 3
Dependent Claim
130 words
A sort processing apparatus comprising: a plurality of sort cells; sort processing means for serially connecting said sort cells and for performing a merge sort on two sets of input data so as to simultaneously perform sort processing of said two sets of input data; an external memory, having an address space, commonly used as a buffer memory by said sort cells; and address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU2## and wherein m=1 to n-1.
Claim 4
Dependent Claim
130 words
A sort processing apparatus comprising: a plurality of sort cells; sort processing means for serially connecting said sort cells and for performing a merge sort on two sets of input data so as to simultaneously perform sort processing of said two sets of input data; an external memory, having an address space, commonly used as a buffer memory by said sort cells; and address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU2## and wherein m=1 to n-1.
Claim 5
Dependent Claim
19 words
An apparatus according to claim 2, wherein address outputs from said address assigning means are wired-ORed to one another.
Claim 6
Dependent Claim
22 words
An apparatus according to claim 2, wherein said sort processing means and said address assigning means are integrated on a semiconductor chip.
Claim 7
Dependent Claim
30 words
An apparatus according to claim 2, wherein each of said n sort cells includes a register for temporarily storing a processing result from a previous one of said sort cells.
Claim 8
Dependent Claim
21 words
An apparatus according to claim 5, wherein outputs from each said registers of said sort cells are wired-ORed to one another.
Claim 9
Dependent Claim
193 words
A sort processing apparatus in which 2 n data can be simultaneously processed comprising: an external memory having an address space; a plurality of sort cells, connected in series, for performing a merge sort on two sets of input data, wherein each of said sort cells includes: a buffer memory for temporarily storing said two sets of input data; a sort executing unit for executing a sort on said two sets of data stored in said buffer memory; and a memory bus for connecting said sort executing unit to said buffer memory; address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU3## and wherein m=1 to n-1; means for commonly connecting said memory buses of said sort cells to one another and to said external memory; and means for controlling access timings of said memory buses by said sort executing units.
Claim 10
Dependent Claim
193 words
A sort processing apparatus in which 2 n data can be simultaneously processed comprising: an external memory having an address space; a plurality of sort cells, connected in series, for performing a merge sort on two sets of input data, wherein each of said sort cells includes: a buffer memory for temporarily storing said two sets of input data; a sort executing unit for executing a sort on said two sets of data stored in said buffer memory; and a memory bus for connecting said sort executing unit to said buffer memory; address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each of said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU3## and wherein m=1 to n-1; means for commonly connecting said memory buses of said sort cells to one another and to said external memory; and means for controlling access timings of said memory buses by said sort executing units.
Claim 11
Dependent Claim
19 words
An apparatus according to claim 7, wherein said plurality of sort executing units are integrated on a semiconductor chip.
Claim 12
Dependent Claim
152 words
A sort processing apparatus comprising: a plurality of sort cells; sort processing means for serially connecting said sort cells and for performing a merge sort on two sets of input data so as to simultaneously perform sort processing on said two sets of input data; an external memory, having an address space, connected to each of said sort cells; address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU4## and wherein m =1 to n-1; common memory bus means for connecting each said sort cell to said external memory; and means for controlling access timings of said common memory bus means.
Claim 13
Dependent Claim
152 words
A sort processing apparatus comprising: a plurality of sort cells; sort processing means for serially connecting said sort cells and for performing a merge sort on two sets of input data so as to simultaneously perform sort processing on said two sets of input data; an external memory, having an address space, connected to each of said sort cells; address assigning means for dividing said address space of said external memory into memory areas and for assigning a memory capacity, which corresponds to an ordinal number of each said sort cells, to each said memory area, wherein said memory capacity of said nth sort cell includes addresses 0 to 2 n -1, wherein an mth sort cell includes addresses ##EQU4## and wherein m =1 to n-1; common memory bus means for connecting each said sort cell to said external memory; and means for controlling access timings of said common memory bus means.
Claim 14
Dependent Claim
18 words
An apparatus according to claim 9, wherein said plurality of sort cells are integrated on a semiconductor chip.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-04-24 | 1998-10-24 | 1999-04-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-04-24 | 2002-10-24 | 2003-04-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-04-24 | 2006-10-24 | 2007-04-25 | $7700.00 | Window Closed / Lapsed |