System and method of scalable transaction processing

#The present invention relates to parallel processing of transaction requests, and more specifically to parallel processing of transaction requests through a scalable pipelined architecture.

#In conventional transaction processing systems, transaction requests are processed on general-purpose processing hardware that executes software or firmware. Each transaction request may include multiple, sequential subtasks that must be completed sequentially to process the task as a whole. These subtasks in turn include discrete operational elements, such as compute or memory access functions. As each task is received, the conventional transaction processing system processes each subtask sequentially by performing the operations instructed by the first subtask, then the second, and so on. These operations may include reading or writing data, storing or loading operands, performing logical computations, manipulating data structures, or branching to a different set of instructions altogether. In most inefficient architectures, the transaction processor is fully dedicated to a given transaction request, therefore the subtasks of each transaction request are completed in sequence regardless of processor idle time. Some transaction processors may begin to process the next transaction request while waiting for results from the current transaction request subtask. For example, the current transaction request subtask may include an external device read instruction. After the processor makes the read request using the correct protocol, it waits for the requested read data to arrive. While the processor is waiting, it is free to begin the processing of a subtask from a different transaction request. This involves the processor storing current data, state information, and status to memory then loading the new subtask instructions into its registers. The processor begins to process the new subtask until the data arrives from the previous subtask request. At that point, the processor can proceed to the next subtask of the original transaction request. The ability to switch between subtasks of different transaction requests allows a more efficient use of processor cycles; however, the sequential nature of the task processing fundamentally limits throughput.

#With the explosive growth of the use of digital data and networking, the numbers of transactions that transaction processing systems are required to handle per unit of time has significantly increased. This growth has outpaced the advances in processor speeds, such that the performance of conventional transaction processing does not meet the market demand. As transaction volumes increase, the traditional model of sequential processing, even with the ability to swap subtasks while waiting for results, is increasingly becoming a limiting process. One solution has been to provide a transaction processing system with more than one processor. However, each processor still requires overhead to swap the tasks or subtasks to which it is assigned. This technique does not relieve the need for additional overhead consumed by subtask swapping. Subtasks must usually be processed sequentially in order to maintain the integrity of the overall task. Parallel processing of subtasks may mean that subtasks are processed out of order. Therefore, typical parallel processing must use additional overhead to ensure orderly completion of subtasks.

#The foregoing and other advantages and features of the invention will become more apparent from the detailed description of exemplary embodiments of the invention given below with reference to the accompanying drawings, in which:

#FIG. 1A is a diagram of a conventional high-level conventional transaction processor system with a single processing element connected to a single memory source;

#FIG. 1B is a timeline of the throughput for a conventional transaction processor;

#The present invention is a parallel transaction processor architecture and an associated apparatus. Specifically, the architecture and apparatus support the processing of multiple transaction requests and their associated subtasks in a parallel pipelined fashion, with individual processing elements assigned to specific subtask categories.

#Referring now to the drawings, where like reference numerals designate like elements, there is shown in FIG. 1A a diagram of conventional transaction processing, including a primary task 110, a primary task 120, a primary task 130, a processing element 140, and a memory 150. Primary task 110 is further divided into a subtask P1S1 111, a subtask P1S2 112, a subtask P1S3 113, and a subtask P1Sn 114. Primary task 120 is further divided into a subtask P2S1 121, a subtask P2S2 122, a subtask P2S3 123, and a subtask P2Sn 124. Primary task 130 is further divided into a subtask P3S1 131, a subtask P3S2 132, a subtask P3S3 133, and a subtask P3Sn 134. Primary task 110, primary task 120, and primary task 130 are tasks to be processed by processing element 140. Processing element 140 works on P1S1 111 of primary task 110 first. The subtasks for each primary task 110 must be completed in order. In other words, P1S1 111 must be completed before processing on P1S2 112 begins, P1S2 112 must be completed before processing on P1S3 113 begins, and so on. However, the completion of a subtask, for example P1S2 112, may require waiting for a response from an external process (not shown). Since subtask P1S2 112 must be completed before processing of subtask P1S3 113 may commence, processing element 140 is free to begin processing another subtask from a different primary task, for example, P2S1 121. While the processing of subtasks within a primary task is sequentially dependent, no such relationship exists between primary tasks, so that the processing of primary task 110, primary task 120, and primary task 130 do not necessarily need to be completed in their queue order; for example, primary task 130 may be completed before primary task 110 is completed.

#Processing element 140 is a serial processor: it can only process one subtask at a time. Although it may process another subtask while waiting for results to return from a previous operation, processing element 140 must first store the contents of its registers in memory for the current subtask before loading the operands for the new subtask. This switching context consumes processing power and takes time. The throughput results of processing element 140 can be seen in FIG. 1B as a timeline 160. Timeline 160 is an example representation of the processing timeline inside processing element 140. In this example, processing element 140 processes subtask P1S1 111 and therefore P1S1 111 is the first completed operation. Next, P1S2 112 is completed, then P2S1 121 and so on. Since processing element 140 is processing each subtask of each primary task serially, the total amount of time spent on processing all of the primary tasks is equal to the sum of times spent processing each subtask.