Electrical computers and digital processing systems: processing – Architecture based instruction processing
Reexamination Certificate
2001-02-14
2004-05-25
Kim, Kenneth S. (Department: 2181)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
C712S201000, C712S211000, C712S248000
Reexamination Certificate
active
06742107
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data processing device such as a processor, and more particularly, to a data processing device which eliminates the need for reading an instruction sequence, searches a memory in correspondence with input data, and executes a process for the input data according to a search result, in order to quickly process a series of data (stream data) such as time-series data generated in a sampling cycle, etc.
2. Description of the Related Art
There are a great many cases in which a series of data (stream data) such as communication packets for use in a network communication, video/audio data, time-series data generated from each type of a sensor in a sampling cycle, data read/written from/to a disk, arithmetic operation data of a data flow processor, communication data between processors in a parallel computer, and the like is processed. The stream data process referred to here has one or a plurality of the following characteristics.
A) Data having a fixed word length is input to a processing device at a constant speed or intermittently.
B) A plurality of data types are sometimes multiplexed into stream data.
C) A process output can be new stream data.
D) A process output can be buffered in a memory.
E) Input or output stream data can be plural.
F) A process sequence can be configured with a finite state machine.
G) A table search is included as one of process capabilities. The table search is sometimes made by using a stream data word as a key.
H) A special arithmetic operation is included as one of the process capabilities. The arithmetic operation must be performed for a stream data word.
Here, the finite state machine is also the name of an automaton the capability of which is in the lowest class in a sense defined by the theory of formal languages. In this specification, the term “finite state machine” is unavoidably used. This means a state machine that is defined by a finite state and a state transition in a general sense.
Stream data is transferred to a processing device such as a computer, etc., via a transmission line such as a network, a bus, etc., and is processed.
The speed of such stream data has been becoming faster year by year with an increase in a device speed. By way of example, for a communication packet, the speed of 1 Gbps (125 MB/sec) to 4 Gbps (500 MB/sec) is required even at present, and a further increase in the speed is promised. For example, if stream data with a 1-Gbps transfer speed is processed in units of 1 byte, 8 ns (125 MHz) is required to process the data. Even if this stream data is processed in units of 4 bytes, 32 ns (31.25 MHz) is required. The process speed becomes a problem if data is processed at high speed. Furthermore, in terms of capabilities, a complex process such as an image process, a communication process, etc. is required, and at the same time, it is demanded to allow the contents of a process to be flexibly changed.
The present invention aims at general-purpose data processes such as a stream data process, etc., and particularly relates to a method configuring a processing device (processor) that can change the contents of a process.
The conventional techniques for processing stream data are broadly classified into hardware and software methods. Theoretically, a stream data can be implemented by both hardware and software methods. However, processing performance and ease of a capability change must be considered.
The hardware method is a widely used method implementing process capabilities with dedicated hardware. With a dedicated hardware process, dedicated hardware is configured to allow stream data to be processed at the same speed as an input/output speed. Therefore, input stream data can be sequentially processed each time one word is input, without buffering the data (sequential processing method). However, a transfer rate and a processing rate may be sometimes adjusted via some elastic buffer although buffering is not needed as described above. The sequential processing method has an advantage that its process delay normally becomes smaller than that in a batch processing method with which the whole of a series of stream data is processed after being stored in a memory.
The performance of a current CMOS device is approximately 250 MHz. Therefore, a small delay and high performance can be implemented with the sequential processing method by suitably adjusting a word to be processed. At this time, however, a possibility of a capability change becomes a problem. A conventional solution to this problem is, for example, a method using a reconfigurable device such as an FPGA (Field Programmable Gate Array), a PLD (Programmable Logic Device), etc. The method using a reconfigurable (programmable) device is used in some Internet routers. However, since the circuitry amount that can be implemented with the current programmable devices is limited and its performance is low, this method is used only in limited fields. Even if a large-scale and high-performance programmable device becomes available with technological advances in the future, also the transfer speed of stream data using the same technology is expected to increase. Therefore, a field to which a reconfigurable device is applied will be limited only to a field of low performance.
The software method is a method implementing process capabilities with software by using a general-purpose or a dedicated processor. The software method has an advantage that a capability can be changed with ease. This is because capabilities are implemented by software. Furthermore, since an actually existing processor is used in a computer system, this method has another advantage that only a minimum of hardware is required for implementation, which leads to a reduction in cost.
However, there are some problems in terms of performance. Normally, a plurality of instructions must be executed to process one stream data. Therefore, a processor must run at a speed of several multiples of the transfer speed of stream data. Assuming that 10 instructions must be executed to process one stream data, a processor which runs at 312.5 MHz or faster must be fully operated to process 1-Gbps stream data in units of 4 bytes. That is, the software method is effective if the transfer speed of stream data is low, but has a difficulty in processing stream data with high speed that is close to the operating frequency of a processor.
Furthermore, since a computer normally runs under an administration system such as an operating system, etc., the computer cannot immediately start its processing in all cases when stream data is generated. Therefore, a series of stream data is stored in a memory and batch-processed after being accumulated to some amount, so that processed data is obtained or again transferred to another location. Such a batch processing method is a representative method adopted in a normal computer system. With this method, stream data is stored in a memory via an I/O bus. Upon completion of storing a series of data, a computer processes the data with software, and transfers the result of the process to another location via an I/O bus upon terminating the process. Specifically, many computer network processes, image processes, Internet routers, etc. adopt this method. However, because data is stored in a memory, this method poses a delay occurrence problem. For this reason, the processing is performed intermittently although its processing ability is sufficient, and the sequential processing method with a small delay cannot be adopted. This is widely known as a real (actual) time problem.
In summary, the hardware method enables high-speed processing, but has a difficulty in capability change. In the meantime, the software method can flexibly change a capability, but has a problem in data processing performance. Therefore, a processing method that can flexibly change a capability, and can sequentially process data is demanded.
A conventional processor is a stored program type called a Neumann type processor, and is compose
Kim Kenneth S.
Staas & Halsey , LLP
LandOfFree
Dynamically configured processing of composite stream input... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamically configured processing of composite stream input..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamically configured processing of composite stream input... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214876