Sorting apparatus

Claim 2

A sorting apparatus comprising: a plurality of sort processors, wherein each of said sort processors includes (a) a local memory for storing a first output string, which is to be outputted from a preceding sort processor, as a first data string, said local memory including a low speed portion, and a high speed portion having an access speed quicker than an access speed of said low speed portion, a first portion of said first data string being stored in the high speed portion of the local memory and a second portion of said first data string being stored in the low speed portion of the local memory; and (b) a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor, and the first data string stored in said local memory and for outputting a merge sort result to a succeeding sort processor; wherein, to read said first data string from said local memory, said sort core unit includes control means for returning data of said first portion of said first data string from said high speed portion to said sort core unit, for transferring data of said second portion of said first data string from said low speed portion to an address in said high speed portion as data is returned from said high speed portion to said sort core unit, and for returning data of said second portion of said first data string from said high speed portion to said sort core unit at high speed.

Claim 3

A sorting apparatus comprising a plurality of sort processors connected in a pipe-line fashion, and a plurality of memories connected to said plurality of sort processors; wherein at least one said sort processors is connected to at least two of said plurality of memories and includes: means for receiving an external identification signal for identifying one of said at least two of said plurality of memories to be used in sorting, storing means for storing a first output string, which is outputted from a preceding sort processor, in said one of said at least two memories identified by said identification signal, as a first data string, and a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in said identified memory, and for outputting a merge sort result to a succeeding sort processor.

Claim 4

A sorting apparatus comprising a plurality of sort processors connected in a pipe-line fashion, and a plurality of memories connected to said plurality of sort processors; wherein at least one said sort processors is connected to at least two of said plurality of memories and includes: means for receiving an external identification signal for identifying one of said at least two of said plurality of memories to be used in sorting, storing means for storing a first output string, which is outputted from a preceding sort processor, in said one of said at least two memories identified by said identification signal, as a first data string, and a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in said identified memory, and for outputting a merge sort result to a succeeding sort processor.

Claim 5

A sorting apparatus comprising: a plurality of sort processors connected in a pipe-lined fashion, and a plurality of external local memories corresponding to said plurality of sort processors, for storing a first output string, which is outputted from a preceding sort processor, as a first data string. wherein each of said plurality of sort processors includes a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in one of said external local memories corresponding to said sort processor, and wherein one of said external local memories is situated in a low portion of a common memory and another one of said external local memories is situated in a high portion of the common memory, and wherein a sort processor corresponding to the external local memory situated in the high portion of the common memory includes an inverter for inverting an address to be accessed prior to accessing said address in said common memory, so as to access said high portion of the common memory.

Claim 6

A sorting apparatus comprising: a plurality of sort processors connected in a pipe-lined fashion, and a plurality of external local memories corresponding to said plurality of sort processors, for storing a first output string, which is outputted from a preceding sort processor, as a first data string. wherein each of said plurality of sort processors includes a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in one of said external local memories corresponding to said sort processor, and wherein one of said external local memories is situated in a low portion of a common memory and another one of said external local memories is situated in a high portion of the common memory, and wherein a sort processor corresponding to the external local memory situated in the high portion of the common memory includes an inverter for inverting an address to be accessed prior to accessing said address in said common memory, so as to access said high portion of the common memory.

Claim 7

A sorting apparatus comprising: a plurality of sort processors connected in a pipe-lined fashion, and a plurality of external local memories corresponding to said plurality of sort processors, for storing a first output string, which is outputted from a preceding sort processor, as a first data string. wherein each of said plurality of sort processors includes a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in one of said external local memories corresponding to said sort processor, wherein one of said external local memories is situated in a first portion of a common memory and another one of said external local memories is situated in a second portion of the common memory, and wherein said plurality of sort processors are divided into a first group and a second group, the sort processors in each group being separately arranged in a pipeline manner to create two distinct sorting paths, and wherein a sort processor in said first group and a sort processor in said second group correspond to the external local memories situated in said common memory.

Claim 8

A sorting apparatus comprising: a plurality of sort processors connected in a pipe-lined fashion, and a plurality of external local memories corresponding to said plurality of sort processors, for storing a first output string, which is outputted from a preceding sort processor, as a first data string. wherein each of said plurality of sort processors includes a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in one of said external local memories corresponding to said sort processor, wherein one of said external local memories is situated in a first portion of a common memory and another one of said external local memories is situated in a second portion of the common memory, and wherein said plurality of sort processors are divided into a first group and a second group, the sort processors in each group being separately arranged in a pipeline manner to create two distinct sorting paths, and wherein a sort processor in said first group and a sort processor in said second group correspond to the external local memories situated in said common memory.

Claim 9

A sort processor for a sorting apparatus having a plurality of sort processors connected in pipeline-fashion, said sort processor comprising: (a) a local memory for storing a first output string, which is to be outputted from a preceding sort processor, as a first data string, said local memory including a low speed portion, and a high speed portion having an access speed quicker than an access speed of said low speed portion, a first portion of said first data string being stored in the high speed portion of the local memory and a second portion of said first data string being stored in the low speed portion of the local memory; and (b) a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor, and the first data string stored in said local memory and for outputting a merge sort result to a succeeding sort processor; wherein, to read said first data string from said local memory, said sort core unit includes control means for returning data of said first portion of said first data string from said high speed portion to said sort core unit, for transferring data of said second portion of said first data string from said low speed portion to an address in said high speed portion as data is returned from said high speed portion to said sort core unit, and for returning data of said second portion of said first data string from said high speed portion to said sort core unit at high speed.

Claim 10

A sort processor for a sorting apparatus having a plurality of sort processors connected in pipeline-fashion, said sort processor comprising: (a) a local memory for storing a first output string, which is to be outputted from a preceding sort processor, as a first data string, said local memory including a low speed portion, and a high speed portion having an access speed quicker than an access speed of said low speed portion, a first portion of said first data string being stored in the high speed portion of the local memory and a second portion of said first data string being stored in the low speed portion of the local memory; and (b) a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor, and the first data string stored in said local memory and for outputting a merge sort result to a succeeding sort processor; wherein, to read said first data string from said local memory, said sort core unit includes control means for returning data of said first portion of said first data string from said high speed portion to said sort core unit, for transferring data of said second portion of said first data string from said low speed portion to an address in said high speed portion as data is returned from said high speed portion to said sort core unit, and for returning data of said second portion of said first data string from said high speed portion to said sort core unit at high speed.

Claim 11

A sort processor for a sorting apparatus having a plurality of sort processors connected in pipeline-fashion, said sort processor comprising: means for receiving an external identification signal for identifying one of said at least two of said plurality of memories to be used in sorting, storing means for storing a first output string, which is outputted from a preceding sort processor, in said one of said at least two memories identified by said identification signal, as a first data string, and a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in said identified memory, and for outputting a merge sort result to a succeeding sort processor.

Claim 12

A sort processor for a sorting apparatus having a plurality of sort processors connected in pipeline-fashion, said sort processor comprising: means for receiving an external identification signal for identifying one of said at least two of said plurality of memories to be used in sorting, storing means for storing a first output string, which is outputted from a preceding sort processor, in said one of said at least two memories identified by said identification signal, as a first data string, and a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor and the first data string stored in said identified memory, and for outputting a merge sort result to a succeeding sort processor.

Claim 13

A sorting apparatus comprising: a first plurality of sort processors connected in a pipe-lined fashion to form a first sorting path; a second plurality of sort processors, connected in a pipe-lined fashion to form a second sorting path; wherein each of the sort processors of the first plurality of sort processors and the second plurality of sort processors includes: (a) a local memory for storing a first output string, which is to be outputted from a preceding sort processor, as a first data string; and (b) a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor, and the first data string stored in said local memory and for outputting a merge sort result to a succeeding sort processor; wherein one sort processor of said first plurality of sort processors requires additional memory of a first size for storing a corresponding first output string and one sort processor of said second plurality of sort processors requires additional memory of a second size for storing a corresponding first output string; and an external memory, having a size greater than said first size and said second size, connected to the one sort processor of the first plurality of sort processors to provide access to a first part of the external memory, and connected to the one sort processor of the second plurality of sort processors to provide access a second part of the external memory.

Claim 14

A sorting apparatus comprising: a first plurality of sort processors connected in a pipe-lined fashion to form a first sorting path; a second plurality of sort processors, connected in a pipe-lined fashion to form a second sorting path; wherein each of the sort processors of the first plurality of sort processors and the second plurality of sort processors includes: (a) a local memory for storing a first output string, which is to be outputted from a preceding sort processor, as a first data string; and (b) a sort core unit for merge sorting a second output string, which is outputted from said preceding sort processor, and the first data string stored in said local memory and for outputting a merge sort result to a succeeding sort processor; wherein one sort processor of said first plurality of sort processors requires additional memory of a first size for storing a corresponding first output string and one sort processor of said second plurality of sort processors requires additional memory of a second size for storing a corresponding first output string; and an external memory, having a size greater than said first size and said second size, connected to the one sort processor of the first plurality of sort processors to provide access to a first part of the external memory, and connected to the one sort processor of the second plurality of sort processors to provide access a second part of the external memory.

Claim 15

The sorting apparatus of claim 7, further comprising: a plurality of external memories, each external memory being connected to one sort processor of the first plurality of sort processors to provide access to a first part of the external memory, and connected to one sort processor of the second plurality of sort processors to provide access a second part of the external memory.

Claim 16

The sorting apparatus of claim 7, further comprising address adjusting means, connected between the external memory and the one sort processor of the second plurality of sort processors, for adjusting an address from the sort processor to be within addresses in said second part of said external memory.

Claim 17

The sorting apparatus of claim 9, wherein said address adjusting means includes an inverter.