US 6,876,561 B2Grant
Scratchpad memory
Issue Date:2005-04-05
•13 Claims
•9 Drawing Sheets
Abstract
An integrated circuit includes a random access memory (RAM) storage and a controller both located on one semiconductor chip. The controller is coupled to read data from and write data to the RAM storage. The controller is programmable to perform bitwise operations on data words stored in the RAM.
Metadata
Assignee
- Intel Corporation
Inventors
- Gilbert Wolrich
- Debra Bernstein
- Matthew Adiletta
Application Information
Application Number:US 10/726,757
Filing Date:2003-12-03
Priority Date:1999-12-28
Art Unit:2824
Patent Drawings (9 sheets)
Description
[00002] This application is a continuation of, and claims priority to, U.S. patent application Ser. No. 10/457,337, filed Jun. 9, 2003, now U.S. Pat. No. 6,667, 920, entitled “SCRATCHPAD MEMORY”; which is in turn a continuation of, and claims priority to, U.S. patent application Ser. No. 10/010,334, filed Oct. 22, 2001, now U.S. Pat. No. 6,577,542 entitled “SCRATCHPAD MEMORY”; which is in turn a continuation of, and claims priority to, U.S. patent application Ser. No. 09/473,111, filed Dec. 28, 1999 now U.S. Pat. No. 6,307,789.
Background of the Invention
[00003] Many modern computers have a parallel structure in which several identical processors are capable of performing tasks on incoming instructions and/or data. The parallel structure can handle high instruction and/or data bandwidths if the various tasks are independent. To perform some of the tasks, the processors can access shared resources. Frequently, the shared resources include a data storage device.
Summary of the Invention
[00004] According to one aspect, a integrated circuit includes a random-access memory (RAM) storage and a controller both located on the same semiconductor chip. The controller is coupled to read data from and write data to the RAM storage. The controller is programmable to perform bitwise operations on data words stored in the RAM.
Brief Description of the Drawings
[00005] FIG. 1 is a block diagram of a router based on a multithreaded processor;
[00006] FIG. 2 is a block diagram of a FIFO bus interface of the parallel processor of FIG. 1 ;
[00007] FIG. 3 is a block diagram of one of the parallel processing engines used by the multithreaded processor of FIG. 1 ;
[00008] FIG. 4 is a block diagram of a MAC port coupled to the multithreaded processor of FIG. 1 ;
[00009] FIG. 5A shows the status registers for receive-status data;
[00010] FIG. 5B shows the status registers for transmit-status data;
[00011] FIG. 5C shows the transmit FIFO buffer located in the FIFO bus interface of FIG. 2 ;
[00012] FIG. 6 is a flow chart showing a process for providing ready-status data to scheduler threads;
[00013] FIG. 7 is a block diagram of a shared scratchpad memory;
[00014] FIG. 8A shows a bitwise set operation on a data word;
[00015] FIG. 8B shows a bitwise clear operation on a data word;
[00016] FIG. 8C shows a bitwise increment operation on a data word;
[00017] FIG. 9 is a flow chart showing a process for performing bitwise set and clear operations; and
[00018] FIG. 10 is a flow chart showing a process for performing a bitwise “test and set” and “test and clear” operations.
Description
[00019] FIG. 1 is a block diagram of a router 10 that uses a parallel processor 12, a set of media access chip (MAC) devices 14, 14′, 14″, and a FIFO bus 16. The router 10 performs data switching between source and destination networks 18, 18′, 18″ connected to the MAC devices 14, 14′, 14″. The MAC devices 14, 14′, 14″ are bridges that couple external networks 18, 18′, 18″ to the FIFO bus 16. The processor 12 can execute software to control data routing. By basing control on software, the processor 12 may be more easily modified to accommodate new protocols or data characteristics.
[00020] The router 10 performs data routing in two stages. First, one of the MAC devices 14, 14′, 14″ connected to the source network 18, 18′, 18″ transmits a data packet to the parallel processor 12 via the FIFO bus 16. Second, the parallel processor 12 retransmits the data packet over the FIFO bus 18 to the MAC device 14, 14′, 14″ connected to the destination network 18, 18′, 18″. The data transmissions over the FIFO bus 16 employ 64-byte data packets and proceed via an Ethernet protocol.
[00021] The parallel processor 12 has a parallel data forwarding structure that includes an array of identical processing engines 22a-22f. Each processing engine 22a-22f has an internal structure for executing a plurality of, e.g., four, independent threads.
[00022] Referring to FIGS. 1 and 2 , the processing engines 22a-22f process data packets received from the MAC devices 14, 14′, 14″. To process a data packet, one of the processing engines 22a-22f looks up routing information in a synchronous random-access memory (SRAM) 24 using information from the packet header. The processing engines 22a-22f also move the data packets from a FIFO buffer 58 to a queue in a synchronous dynamic random-access memory (SDRAM) 26. The FIFO buffer 58 temporarily stores data packets received from the MAC devices 14, 14′, 14″. The various queues located in the SDRAM 26 are classified by destination MAC device 14, 14′, 14″ and retransmission priority.
[00023] The processing engines 22a-22f also process data from the queues of the SDRAM 26. This processing includes moving data packets from the queues of the SDRAM 26 to a FIFO buffer 60. The FIFO buffer 60 temporarily stores data prior to retransmission to the MAC devices 14, 14′, 14″ over the FIFO bus 16. Along with the data, associated control and destination information are stored in the FIFO buffer 60 for use in transmitting the data. The associated data is 16 bytes wide.
[00024] The SRAM 24 and SDRAM 26 couple to the processing engines 22a-22f through respective SRAM and SDRAM controllers 34, 36. The SRAM controller 34 has content addressable memory that supports look ups of identification information on the queues of the SDRAM 24. The look-ups use header data from received data packets. The SDRAM controller 36 coordinates data writes to and reads from the queues of the SDRAM 24 that store received data packets.
[00025] The parallel processor 12 has several internal busses 39, 40, 41. An S bus 39 couples the processing engines 22a-22f to a FIFO bus interface 38 (FBI) and to the SRAM controller 34. An M bus 40 couples the processing engines 22a-22f and the FBI 38 to the SDRAM controller 36 and the SDRAM 26. An AMBA bus 41 couples a processor core 44 to the processing engines 22a-22f and the FBI 38.
[00026] The FBI 38 controls data transfers on the FIFO bus 16 and collects status data on the readiness of the ports 28, 30, 32 of the MAC devices 14, 14′, 14″ to participate in data transfers over the FIFO bus 16. The ready status data is collected from the MAC devices 14, 14′, 14″ through a ready bus 42, which is also controlled by the FBI 38.
[00027] Referring again to FIG. 1 , the processor core 44 uses software to perform a variety of functions. The functions may include data packet routing, exception handling, queue management, monitoring of data packet transfers, supporting network management protocols and/or providing local area network emulation.
[00028] The parallel processor 12 includes a PCI bus interface 46 that couples to a PCI bus 48. The PCI bus 48 can support communications between the parallel processor 12 and external processors. The other processors may control and/or reprogram the processor core 44 or other components 22a-22f, 38 of the multiprocessor 12.
[00029] Referring again to FIG. 2 , the connections between the FBI 38 and the processing engines 22a-22f are shown. The FBI 38 includes a control module 50 for the ready bus 42 and a push engine 62. The control module 50 periodically collects receive-ready status data and transmit-ready status data from the MAC devices 14, 14′, 14″. The collected ready status data is stored in a set of status registers 54. The set includes separate registers for storing receive-ready status data and transmit-ready status data. The push engine 62 regularly sends the ready status data over the S bus 39 to scheduler threads located in the processing engines 22a-22f in response to commands from logic internal to the FBI 38.
[00030] The processing engines 22a-22f include separate receive-scheduler and transmit-scheduler threads. The receive-scheduler thread schedules the processing of data received from the FIFO bus 16. The transmit-scheduler thread schedules the processing of data to be transmitted to the FIFO bus 16.
[00031] The receive-scheduler thread assigns data forwarding and header processing tasks to other threads in the processing engines 22a-22f. These tasks include sharing operation of a push engine 62 that transports data from the receive FIFO buffer 58 in the FBI 38 to one of the storage queues in the SDRAM 26.
[00032] The transmit-scheduler thread also assigns data forwarding tasks to other threads in the processing engines 22a-22f. These tasks include sharing in operation of a pull engine 64, which moves data from the storage queues in the SDRAM 26 to the transmit FIFO buffer 60. The tasks also include directing the pull engine 62 to write transmission control and MAC device 14, 14′, 14″ address information to the FIFO buffer 60. Each data packet in the transmit FIFO buffer 60 has associated address and control information that control the retransmission over the FIFO bus 16.
[00033] To control data forwarding by the push and pull engines 62, 64, the execution threads of the processing engines 22a-22f send commands signals to FIFO command queues 66, 68 via a line 70. Components of the FBI 38 can also send commands to the command queues 66, 68 of push and pull engines 62, 64. For example, the ready bus controller 50 can send a command to the queue 66 that causes the push engine 62 to transfer ready status data from the status registers 54 to the processing engines 22a-22f. An arbiter 56 controls transmission of commands from the queues 66, 68 to the push and pull engines 62, 64.
[00034] The push and pull engines 62, 64 perform several types of tasks. The push and the pull engines 62, 64 are involved in bi-directional forwarding of data packets between the FIFO buffers 58, 60 and the SDRAM controller 36. The push and pull engines 62, 64 also operate a large hardware unit 71 located in the FBI 38. The push engine 62 also forwards ready status data from the set of status registers 54 to the receive- and transmit-scheduler threads located in the processing engines 22a-22f.
[00035] The hardware unit 71 performs various operations for the execution threads of the processing engines 22a-22f and includes a hash unit 72 and a scratchpad memory 73. The execution threads operate the hardware unit 71 by sending commands to the queues 66, 68. To perform the operations, the pull engine 64 retrieves input data over the S bus 39 from output transfer registers 80a-80f of the requesting processing engine 22a-22f. The pull engine 64 moves the retrieved data and associated commands to the hardware unit 71. The hardware unit 71 forwards results from the operations to the push engine 62. The push engine 62 uses command information from the command queue 66 and/or pull engine 64 to transmit the results back over the S bus 39 to input transfer registers 78a-78f of the requesting or destination processing engine 22a-22f.
[00036] Referring to FIG. 3 , one embodiment 74 of the processing engines 22a-22f is shown. The processing engines 22a-22f have input/output terminals 75-77 for control signals, address signals, and data. Control signals, address signals, and data are transferred to and from the processing engines 22a-22f over three busses, i.e., the M bus 40, the S bus 39, and the AMBA bus 41. The address signals identify both a processing engine 22a-22f and an execution thread so that external commands can independently address different threads. Data is received at and transmitted from respective input and output transfer registers 78, 80. Each input and output transfer register 78, 80 is assigned to an individual execution thread. To write data to or read data from a particular execution thread, an external device accesses one of the transfer registers 78, 80 assigned to the particular thread.
[00037] Referring to FIG. 4 , the port 28 of the MAC device 14 is shown. The port 28 has transmit and receive FIFO buffers 90, 92 for storing data prior to transmission to and after reception from the FIFO bus 16, respectively. Both buffers 90, 92 have entries of fixed size that are multiples of 64 bytes, i.e., the size of data packets on the FIFO bus 16. The port 28 also includes address decoders and a controller 94. The controller 94 controls both protocol transfers over the FIFO bus 16 and responses to ready status queries from the ready bus 42. The responses to the queries indicate whether the transmit buffer 90 has a 64 byte data packet to transmit and/or whether the receive buffer 92 has space to receive a 64 byte data packet.
[00038] The various ports 28, 30, 32 of the MAC devices 14, 14′, 14″ may support different data transfer rates. The ports 28, 30 of the MAC devices 14, 14′ support transfer rates of about ten or one hundred megabits of data per second. The port 32 of the MAC device 14″ may have a transfer rate of up to about one gigabit per second.
[00039] The ready bus 42 includes control/address and data lines. The control/address lines enable selection of a transaction type and a port 28, 30, 32 of the MAC devices 14, 14′, 14″. The data line transfers receive- and transmit-ready status data to the FBI 38 in response to status queries from the control module 50 for the ready bus 42.
[00040] Referring to 5A, the registers R1, R2, R3 that store receive-ready status data are shown. The registers R1 and R2 store receive-ready status data for individual MAC ports 28, 30, 32. The readiness of each MAC port 28, 30, 32 to transmit a data packet to the FIFO bus 16 is indicated by the value of an associated bit or flag stored in one of the registers R1, R2. One logic value of the bit or flag indicates that the associated port 28, 30, 32 has a data packet ready to transmit, and the other logic value indicates the associated port 28, 30, 323 has no ready data packets. Different ports 28, 30, 32 may have data packets of different sizes, but the receive scheduler thread knows the packet size associated with each port 28, 30, 32.
[00041] The registers R2 and R3 have 32 bits each and thus, can accommodate receive-ready status data for up to 64 different MAC ports 28, 30, 32.
[00042] The register R3 stores a cyclic counter value, which acts as a time stamp for the receive-status data stored in registers R1, R2. The counter value is incremented each time new receive-status data is collected. By comparing the counter value to a previously received counter value, the scheduler thread can determine whether the present receive-status data is new or stale, i.e., whether the data has already been seen.
[00043] Referring to FIG. 5B , the registers R4, R5, R6 that store transmit-ready status data are shown. The registers R4 and R4 store transmit-ready status data for individual MAC ports 28, 30, 32. Each MAC port 28, 30, 32 has an associated bit or flag in one of the registers R4 and R4. One logic value of the bit or flag indicates that the associated port 28, 30, 32 has enough space to receive a data packet, and the other logic value indicates the associated port 28, 30, 32 does not have enough space.
[00044] The registers R4 and R5 have a total of 64 bits and thus, can report transmit ready status for up to 64 MAC ports 28, 30, 32.
[00045] Referring to FIG. 5C , the number stored in register R6 indicates the position of a remove pointer 96 in the transmit FIFO buffer 60. For an embodiment in which the transmit FIFO buffer 60 has sixteen entries, the position of the remove pointer is represented as a 4-bit number.
[00046] Since the FBI 38 transmits 64-byte data packets from the buffer 60 according to a FIFO scheme, the remove pointer 96 indicates which data packets are scheduled but not transmitted. The position of the pointer 96 can be used to determine which MAC ports 28, 30, 32 have been scheduled to receive a data packet but have not yet received a data packet. Such ports 28, 30, 32 may have status data in registers R4, R5 indicating an availability to receive a data packet even though the available space has already been assigned to a waiting data packet.
[00047] The transmit scheduler thread can use the position of the remove pointer 96 to interpret transmit-ready status data of the registers R4, R5. From the position of the remove pointer 96, the transmit scheduler thread identifies MAC ports 28, 30, 32 already scheduled to receive a data packet. The transmit scheduler thread does not schedule a new data packet for such ports, because the waiting and already scheduled data packet may take the available space therein.
[00048] In the multiprocessor 12, the collection of ready status data is asynchronous with respect to scheduling of data packet transfers. The asynchronous relationship enables both the collection of ready status data and the scheduling of data packets to have higher effective bandwidths. The asynchronous relationship also introduces some unpredictability into latencies associated with the transfer of newly collected ready status data to scheduler threads.
[00049] Referring to FIG. 6 , a process 100 by which the FBI 38 provides ready status data to the scheduler threads is shown. The FBI 38 performs 102 a collection cycle in which new ready status data is obtained from the MAC devices 14, 14′, 14″ interactively via the ready bus 42. In response to completing the collection cycle, the FBI 38 performs an unsolicited transfer 104 of the newly collected ready status data to the input transfer registers 78a-78f assigned to the scheduler threads. In an unsolicited data transfer, the destination device for the transfer does not request the transfer. The transfer of ready status data from the FBI 38 to destination processing engines 22a-22f and scheduling threads proceeds without any request from the processing engines 22a-22f. Instead, the FBI 38 automatically performs the transfer in response to finishing a collection cycle for the ready status data. The completion of each collection cycle causes issuance of a command to the push engine 62, which transfers the ready bus data to the processing engines 22a-22f. After completing the transfer, the FBI 38 loops back 106 to collect new ready status data.
[00050] Making transfers of new ready status data unsolicited lowers latencies for delivering such data to scheduler threads. Since latencies in delivering such data can cause scheduling errors, making the transfer of ready status data unsolicited can lower numbers of occurrences of scheduling errors. The data is transmitted from respective input and output transfer registers 78, 80. Each input and output transfer register 78, 80 is assigned to an individual execution thread. To write data to or read data from a particular execution thread, an external device accesses one of the transfer registers 78, 80 assigned to the particular thread.
[00051] Referring to FIG. 4 , the port 28 of the MAC device 14 is shown. The port 28 has transmit and receive FIFO buffers 90, 92 for storing data prior to transmission to and after reception from the FIFO bus 16, respectively. Both buffers 90, 92 have entries of fixed size that are multiples of 64 bytes, i.e., the size of data packets on the FIFO bus 16. The port 28 also includes address decoders and a controller 94. The controller 94 controls both protocol transfers over the FIFO bus 16 and responses to ready status queries from the ready bus 42. The responses to the queries indicate whether the transmit buffer 90 has a 64 byte data packet to transmit and/or whether the receive buffer 92 has space to receive a 64 byte data packet.
[00052] The various ports 28, 30, 32 of the MAC devices 14, 14′, 14″ may support different data transfer rates. The ports 28, 30 of the MAC devices 14, 14′ support transfer rates of about ten or one hundred megabits of data per second. The port 32 of the MAC device 14″ may have a transfer rate of up to about one gigabit per second.
[00053] The ready bus 42 includes control/address and data lines. The control/address lines enable selection of a transaction type and a port 28, 30, 32 of the MAC devices 14, 14′, 14″. The data line transfers receive- and transmit-ready status data to the FBI 38 in response to status queries from the control module 50 for the ready bus 42.
[00054] Referring to FIG. 5A , the registers R1, R2, R3 that store receive-ready status data are shown. The registers R1 and R2 store receive-ready status data for individual MAC ports 28, 30, 32. The readiness of each MAC port 28, 30, 32 to transmit a data packet to the FIFO bus 16 is indicated by the value of an associated bit or flag stored in one of the registers R1, R2. One logic value of the bit or flag indicates that the associated port 28, 30, 32 has a data packet ready to transmit, and the other logic value indicates the associated port 28, 30, 323 has no ready data packets. Different ports 28, 30, 32 may have data packets of different sizes, but the receive scheduler thread knows the packet size associated with each port 28, 30, 32.
[00055] The registers R2 and R3 have 32 bits each and thus, can accommodate receive-ready status data for up to 64 different MAC ports 28, 30, 32.
[00056] The register R3 stores a cyclic counter value, which acts as a time stamp for the receive-status data stored in registers R1, R2. The counter value is incremented each time new receive-status data is collected. By comparing the counter value to a previously received counter value, the scheduler thread can determine whether the present receive-status data is new or stale, i.e., whether the data has already been seen.
[00057] Referring to FIG. 5B , the registers R4, R5, R6 that store transmit-ready status data are shown. The registers R4 and R4 store transmit-ready status data for individual MAC ports 28, 30, 32. Each MAC port 28, 30, 32 has an associated bit or flag in one of the registers R4 and R4. One logic value of the bit or flag indicates that the associated port 28, 30, 32 has enough space to receive a data packet, and the other logic value indicates the associated port 28, 30, 32 does not have enough space.
[00058] The registers R4 and R5 have a total of 64 bits and thus, can report transmit ready status for up to 64 MAC ports 28, 30, 32.
[00059] Referring to FIG. 5C , the number stored in register R6 indicates the position of a remove pointer 96 in the transmit FIFO buffer 60. For an embodiment in which the transmit FIFO buffer 60 has sixteen entries, the position of the remove pointer is represented as a 4-bit number.
[00060] Since the FBI 38 transmits 64-byte data packets from the buffer 60 according to a FIFO scheme, the remove pointer 96 indicates which data packets are scheduled but not transmitted. The position of the pointer 96 can be used to determine which MAC ports 28, 30, 32 have been scheduled to receive a data packet but have not yet received a data packet. Such ports 28, 30, 32 may have status data in registers R4, R5 indicating an availability to receive a data packet even though the available space has already been assigned to a waiting data packet.
[00061] The transmit scheduler thread can use the position of the remove pointer 96 to interpret transmit-ready status data of the registers R4, R5. From the position of the remove pointer 96, the transmit scheduler thread identifies MAC ports 28, 30, 32 already scheduled to receive a data packet. The transmit scheduler thread does not schedule a new data packet for such ports, because the waiting and already scheduled data packet may take the available space therein.
[00062] In the multiprocessor 12, the collection of ready status data is asynchronous with respect to scheduling of data packet transfers. The asynchronous relationship enables both the collection of ready status data and the scheduling of data packets to have higher effective bandwidths. The asynchronous relationship also introduces some unpredictability into latencies associated with the transfer of newly collected ready status data to scheduler threads.
[00063] Referring to FIG. 6 , a process 100 by which the FBI 38 provides ready status data to the scheduler threads is shown. The FBI 38 performs 102 a collection cycle in which new ready status data is obtained from the MAC devices 14, 14′, 14″ interactively via the ready bus 42. In response to completing the collection cycle, the FBI 38 performs an unsolicited transfer 104 of the newly collected ready status data to the input transfer registers 78a-78f assigned to the scheduler threads. In an unsolicited data transfer, the destination device for the transfer does not request the transfer. The transfer of ready status data from the FBI 38 to destination processing engines 22a-22f and scheduling threads proceeds without any request from the processing engines 22a-22f. Instead, the FBI 38 automatically performs the transfer in response to finishing a collection cycle for the ready status data. The completion of each collection cycle causes issuance of a command to the push engine 62, which transfers the ready bus data to the processing engines 22a-22f. After completing the transfer, the FBI 38 loops back 106 to collect new ready status data.
[00064] Making transfers of new ready status data unsolicited lowers latencies for delivering such data to scheduler threads. Since latencies in delivering such data can cause scheduling errors, making the transfer of ready status data unsolicited can lower numbers of occurrences of scheduling errors.
[00065] Referring to FIG. 7 , the scratchpad memory 73 is shown. The scratchpad memory 73 includes RAM storage 110 and a controller 112 to operate the RAM storage 110. The RAM storage 110 can store, e.g., about 1,024 words having lengths of 32 bits each. The controller 112 has decode and control hardware that provide read and write operations for accessing the RAM storage 110. The controller 112 has additional hardware that provides support for performing bitwise operations on individual data words stored in the RAM storage 110.
[00066] The scratchpad memory 73 interfaces with other devices through the pull and push engines 64, 62. The pull engine 64 provides input commands, data and associated storage addresses to the controller 112. The data may include data words to write to the scratchpad memory 73 and mask words that define bit locations affected by the bitwise operations in the scratchpad memory 73. The push engine 62 receives output commands, data, and associated destination addresses from the controller 112. In some embodiments, the push engine 62 also sends read commands to the controller 112, because reads only require command and address signals, i.e., no data is inputted to the scratchpad memory 73.
[00067] The pull and push engines 64, 62 enable any of the processing engines 22a-22f to use the scratchpad memory 73. The scratchpad memory 73 is a shared on-chip resource. The processing engines 22a-22f and FBI 38, including the scratchpad memory 73, are parts of one integrated circuit, which is located on a semiconductor chip 113. The processing engines 22a-22f share the on-chip scratchpad memory 73 to store data and perform bitwise operations on data. Using a shared resource to perform rare operations and provide storage can reduce overall hardware costs associated with the large array of processing engines 22a-22f.
[00068] The bitwise operations performed by the scratchpad memory 73 include set, clear, “test and set”, “test and clear”, and increment operations. Each bitwise operation uses a 32 bit mask received from the pull engine 64. The mask defines locations at which bitwise manipulations will be performed, e.g., by locations of bits with the value 1 in the mask.
[00069] FIGS. 8A-8C illustrate the bitwise set, clear, and increment operations performed by the scratchpad memory 73. The bitwise operations act on single words from the RAM storage 110.
[00070] Referring to FIG. 8A , the action of the bitwise “set” operation on a data word 114 is shown. The “set” operation sets selected bits of the data word 114 to the value 1. The bit selection is defined by a mask word 116 having the same size as the data word 114. Each location of the data word for which the same bit location in the mask word has the value 1 is selected for the set operation. For the mask word 116, the set operation produces the final word 118 from the data word 114.
[00071] Referring to FIG. 8B , the action of the bitwise “clear” operation on a data word 120 is shown. The “clear” operation fixes selected bits of the data word 120 to the value 0. Again, bit selection is defined by a mask word 122 having the same size as the data word 120. Each location of the data word for which the same location in the mask word has the value 1 is selected for the clear operation. For the mask word 122, the clear operation produces the final word 124 from the data word 120.
[00072] Referring to FIG. 8C , the action of the bitwise increment operation on a data word 126 is shown. The increment operation adds 1 to the data word 126 to produce a final data word 128. The increment operation can be used to implement a cyclic counter in the scratchpad memory 73.
[00073] Referring to FIG. 9 , a process 130 by which the FBI 38 performs the set or clear operations is shown. The operation starts when the pull engine 64 receives 132 a command to perform a set or clear operation from one of the execution threads. The command identifies an address in the scratchpad memory 73 of a data word to be set or cleared. In response to the command, the pull engine 64 retrieves 134 a mask word from the output transfer register 80a-80f associated with the thread requesting the operation. The pull engine 64 transmits 136 a request for the set or clear, as appropriate, and the retrieved mask word to the controller 112 of the scratchpad memory 73. The controller 112 sets or clears 138 a data word of the RAM storage 110. The request identifies the address of the data word to be set or cleared. The bits being set or cleared are defined by the mask word transmitted by the pull engine 64 as already described. After completing the set or clear, the controller 112 sends 140 a completion signal to the push engine 62. The push engine 62 writes 142 an operation completed message to an input transfer register 80a of the execution thread that requested the operation.
[00074] Referring to FIG. 10 , a process 150 by which FBI performs a “test and set” or a “test and clear” operation is shown. The pull engine 64 receives 152 a command to perform a “test and set” or a “test and clear” operation from one of the execution threads. The command identifies the address of the data word of the scratchpad memory 73 upon which the operation will act. The pull engine 64 retrieves 154 a mask word from an output transfer register 80a-80f assigned to the thread requesting the operation. The pull engine 64 transmits 156 a request for the command and the mask word to the controller 112 of the scratchpad memory 73.
[00075] The controller 112 performs 156 a set or clear operation on a data word stored in the RAM storage 110. If the command is for a “test and set”, the set operation is performed. If the command is for a “test and clear”, the clear operation is performed. In either case, the form of the operation performed is defined by the transmitted mask word as already described.
[00076] After completing the appropriate operation, the controller 112 sends 158 both the original data word and operation completed signal to the push engine 62. The push engine 62 writes 160 the original data word and an operation completed message to input transfer registers 80a of the execution thread that requested the operation. Thus, the requesting thread can determine from the data word received whether the set or clear operation has resulted in a change to the data word.
[00077] While various embodiments have been described in the detailed description, the description is intended to illustrate and not to limit the scope of the invention, which is defined by the appended claims. Other aspects, advantages, and modifications are within the scope of the claims.
Claims
1. A processor, comprising:
multiple multi-threaded engines integrated on a single semiconductor chip;
a random access memory integrated on the same semiconductor chip; and
a first memory controller integrated on the same semiconductor chip, the memory controller coupled to the random access memory and coupled to the multiple multi-threaded engines, the memory controller to receive and respond to commands issued by the multiple multi-threaded engines.
2. The processor of claim 1,
wherein the commands received by the first memory controller comprise at least one command specifying bit-wise operations on a location within the random access memory.
3. The processor of claim 1,
wherein the commands received by the first memory controller comprise at least one test-and-set command.
4. The processor of claim 1,
further comprising a single-threaded processor integrated on the same semiconductor chip, the single-threaded processor having a different architecture than at least one of the multiple multi-threaded engines.
5. The processor of claim 1, further comprising a host interface integrated on the same semiconductor chip.
6. The processor of claim 5, wherein the host interface comprises a Peripheral Component Interconnect (PCI) interface.
7. The processor of claim 1, further comprising an interface that is integrated on the same semiconductor chip, the interface comprising an interface to a network component to send and receive packets.
8. The processor of claim 7, wherein the interface comprises an interface to a link layer device.
9. The processor of claim 8, wherein the interface comprises an interface to a bus coupling the network component to the processor.
10. The processor of claim 1, further comprising a second memory controller integrated on the same semiconductor chip, the second memory controller to interface to a random access memory not integrated on the same semiconductor chip, the second memory controller coupled to the multiple multi-threaded engines and to receive and respond to commands received from the multiple multi-threaded engines.
11. The processor of claim 1, further comprising dedicated hash logic integrated on the same semiconductor chip, the dedicated hash logic coupled to the multiple multi-threaded engines.
12. The processor of claim 1, wherein each of the multiple multi-threaded engines comprises:
an instruction control store to store instructions associated with multiple threads;
registers to store multiple contexts respectively associated with the multiple threads, each context comprising a program counter identifying an execution location within a one of the associated threads; and
an arbiter to select a one of the program counters associated with a one of the threads to execute.
13. The processor of claim 1, further comprising:
a host interface integrated on the same semiconductor chip;
an interface, integrated on the same semiconductor chip, to a network component to send and receive packets; and
a second memory controller integrated on the same semiconductor chip, the second memory controller to interface to a random access memory not integrated on the same semiconductor chip, the second memory controller coupled to the multiple multi-threaded engines and to receive and respond to commands received from the multiple multi-threaded engines.
Patent Citations (180)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3373408(A) | 1968-03-01 | Ling | Applicant |
| US3478322(A) | 1969-11-01 | Evans | Applicant |
| US3792441(A) | 1974-02-01 | Wymore et al. | Applicant |
| US3940745(A) | 1976-02-01 | Sajeva | Applicant |
| US4130890(A) | 1978-12-01 | Adam | Applicant |
| US4400770(A) | 1983-08-01 | Chan et al. | Applicant |
| US4514807(A) | 1985-04-01 | Nogi | Applicant |
| US4523272(A) | 1985-06-01 | Fukunaga et al. | Applicant |
| US4745544(A) | 1988-05-01 | Renner et al. | Applicant |
| US4866664(A) | 1989-09-01 | Burkhardt, Jr. et al. | Applicant |
| US5140685(A) | 1992-08-01 | Sipple et al. | Applicant |
| US5142683(A) | 1992-08-01 | Burkhardt, Jr. et al. | Applicant |
| US5155831(A) | 1992-10-01 | Emma et al. | Applicant |
| US5155854(A) | 1992-10-01 | Flynn et al. | Applicant |
| US5168555(A) | 1992-12-01 | Byers et al. | Applicant |
| US5173897(A) | 1992-12-01 | Schrodi et al. | Applicant |
| US5255239(A) | 1993-10-01 | Taborn et al. | Applicant |
| US5263169(A) | 1993-11-01 | Genusov et al. | Applicant |
| US5347648(A) | 1994-09-01 | Stamm et al. | Applicant |
| US5367678(A) | 1994-11-01 | Lee et al. | Applicant |
| US5390329(A) | 1995-02-01 | Gaertner et al. | Applicant |
| US5392391(A) | 1995-02-01 | Caulk, Jr. et al. | Applicant |
| US5392411(A) | 1995-02-01 | Ozaki | Applicant |
| US5392412(A) | 1995-02-01 | McKenna | Applicant |
| US5404464(A) | 1995-04-01 | Bennett | Applicant |
| US5404482(A) | 1995-04-01 | Stamm et al. | Applicant |
| US5432918(A) | 1995-07-01 | Stamm | Applicant |
| US5448702(A) | 1995-09-01 | Garcia, Jr. et al. | Applicant |
| US5450351(A) | 1995-09-01 | Heddes | Applicant |
| US5452437(A) | 1995-09-01 | Richey et al. | Applicant |
| US5459842(A) | 1995-10-01 | Begun et al. | Applicant |
| US5463625(A) | 1995-10-01 | Yasrebi | Applicant |
| US5467452(A) | 1995-11-01 | Blum et al. | Applicant |
| US5517648(A) | 1996-05-01 | Bertone et al. | Applicant |
| US5542070(A) | 1996-07-01 | LeBlanc et al. | Applicant |
| US5542088(A) | 1996-07-01 | Jennings, Jr. et al. | Applicant |
| US5544236(A) | 1996-08-01 | Andruska et al. | Applicant |
| US5550816(A) | 1996-08-01 | Hardwick et al. | Applicant |
| US5557766(A) | 1996-09-01 | Takiguchi et al. | Applicant |
| US5568617(A) | 1996-10-01 | Kametani | Applicant |
| US5574922(A) | 1996-11-01 | James | Applicant |
| US5592622(A) | 1997-01-01 | Isfeld et al. | Applicant |
| US5613071(A) | 1997-03-01 | Rankin et al. | Applicant |
| US5613136(A) | 1997-03-01 | Casavant et al. | Applicant |
| US5623489(A) | 1997-04-01 | Cotton et al. | Applicant |
| US5627829(A) | 1997-05-01 | Gleeson et al. | Applicant |
| US5630130(A) | 1997-05-01 | Perotto et al. | Applicant |
| US5644623(A) | 1997-07-01 | Gutledge | Applicant |
| US5649157(A) | 1997-07-01 | Williams | Applicant |
| US5659687(A) | 1997-08-01 | Kim et al. | Applicant |
| US5680641(A) | 1997-10-01 | Sidman | Applicant |
| US5689566(A) | 1997-11-01 | Nguyen | Applicant |
| US5699537(A) | 1997-12-01 | Sharangpani et al. | Applicant |
| US5717898(A) | 1998-02-01 | Kagan et al. | Applicant |
| US5721870(A) | 1998-02-01 | Matsumoto | Applicant |
| US5742587(A) | 1998-04-01 | Zornig et al. | Applicant |
| US5742782(A) | 1998-04-01 | Ito et al. | Applicant |
| US5742822(A) | 1998-04-01 | Motomura | Applicant |
| US5745913(A) | 1998-04-01 | Pattin et al. | Applicant |
| US5751987(A) | 1998-05-01 | Mahant-Shetti et al. | Applicant |
| US5761507(A) | 1998-06-01 | Govett | Applicant |
| US5761522(A) | 1998-06-01 | Hisanga et al. | Applicant |
| US5781774(A) | 1998-07-01 | Krick | Applicant |
| US5784649(A) | 1998-07-01 | Begur et al. | Applicant |
| US5784712(A) | 1998-07-01 | Byers et al. | Applicant |
| US5796413(A) | 1998-08-01 | Shipp et al. | Applicant |
| US5797043(A) | 1998-08-01 | Lewis et al. | Applicant |
| US5809235(A) | 1998-09-01 | Sharma et al. | Applicant |
| US5809530(A) | 1998-09-01 | Samra et al. | Applicant |
| US5812868(A) | 1998-09-01 | Moyer et al. | Applicant |
| US5828746(A) | 1998-10-01 | Ardon | Applicant |
| US5828863(A) | 1998-10-01 | Barrett et al. | Applicant |
| US5832215(A) | 1998-11-01 | Kato et al. | Applicant |
| US5835755(A) | 1998-11-01 | Stellwagen, Jr. | Applicant |
| US5854922(A) | 1998-12-01 | Gravenstein et al. | Applicant |
| US5860158(A) | 1999-01-01 | Pai et al. | Applicant |
| US5886992(A) | 1999-03-01 | Raatikainen et al. | Applicant |
| US5887134(A) | 1999-03-01 | Ebrahim | Applicant |
| US5890208(A) | 1999-03-01 | Kwon | Applicant |
| US5892979(A) | 1999-04-01 | Shiraki et al. | Applicant |
| US5905876(A) | 1999-05-01 | Pawlowski et al. | Applicant |
| US5905889(A) | 1999-05-01 | Wilhelm, Jr. | Applicant |
| US5915123(A) | 1999-06-01 | Mirsky et al. | Applicant |
| US5937187(A) | 1999-08-01 | Kosche et al. | Applicant |
| US5938736(A) | 1999-08-01 | Muller et al. | Applicant |
| US5940612(A) | 1999-08-01 | Brady et al. | Applicant |
| US5940866(A) | 1999-08-01 | Chisholm et al. | Applicant |
| US5946487(A) | 1999-08-01 | Dangelo | Applicant |
| US5948081(A) | 1999-09-01 | Foster | Applicant |
| US5958031(A) | 1999-09-01 | Kime | Applicant |
| US5961628(A) | 1999-10-01 | Nguyen et al. | Applicant |
| US5970013(A) | 1999-10-01 | Fischer et al. | Applicant |
| US5978838(A) | 1999-11-01 | Mohammed et al. | Applicant |
| US5983274(A) | 1999-11-01 | Hyder et al. | Applicant |
| US6012151(A) | 2000-01-01 | Mano | Applicant |
| US6014729(A) | 2000-01-01 | Lannan et al. | Applicant |
| US6023742(A) | 2000-02-01 | Ebeling et al. | Applicant |
| US6058168(A) | 2000-05-01 | Braband | Applicant |
| US6067585(A) | 2000-05-01 | Hoang | Applicant |
| US6070231(A) | 2000-05-01 | Ottinger | Applicant |
| US6072781(A) | 2000-06-01 | Feeney et al. | Applicant |
| US6073215(A) | 2000-06-01 | Snyder | Applicant |
| US6079008(A) | 2000-06-01 | Clery, III | Applicant |
| US6085215(A) | 2000-07-01 | Ramakrishnan et al. | Applicant |
| US6085294(A) | 2000-07-01 | Van Doren et al. | Applicant |
| US6092127(A) | 2000-07-01 | Tausheck | Applicant |
| US6092158(A) | 2000-07-01 | Harriman et al. | Applicant |
| US6112016(A) | 2000-08-01 | MacWilliams et al. | Applicant |
| US6134665(A) | 2000-10-01 | Klein et al. | Applicant |
| US6141689(A) | 2000-10-01 | Yasrebi | Applicant |
| US6141765(A) | 2000-10-01 | Sherman | Applicant |
| US6144669(A) | 2000-11-01 | Williams et al. | Applicant |
| US6145054(A) | 2000-11-01 | Mehrotra et al. | Applicant |
| US6157955(A) | 2000-12-01 | Narad et al. | Applicant |
| US6160562(A) | 2000-12-01 | Chin et al. | Applicant |
| US6182177(B1) | 2001-01-01 | Harriman | Applicant |
| US6195676(B1) | 2001-02-01 | Spix et al. | Applicant |
| US6199133(B1) | 2001-03-01 | Schnell | Applicant |
| US6201807(B1) | 2001-03-01 | Prasanna | Applicant |
| US6212542(B1) | 2001-04-01 | Kahle et al. | Applicant |
| US6212611(B1) | 2001-04-01 | Nizar et al. | Applicant |
| US6216220(B1) | 2001-04-01 | Hwang | Applicant |
| US6223207(B1) | 2001-04-01 | Lucovsky et al. | Applicant |
| US6223238(B1) | 2001-04-01 | Meyer et al. | Applicant |
| US6223279(B1) | 2001-04-01 | Nishimura et al. | Applicant |
| US6247025(B1) | 2001-06-01 | Bacon | Applicant |
| US6256713(B1) | 2001-07-01 | Audityan et al. | Applicant |
| US6272616(B1) | 2001-08-01 | Fernando et al. | Applicant |
| US6275505(B1) | 2001-08-01 | O'Loughlin et al. | Applicant |
| US6279113(B1) | 2001-08-01 | Vaidya | Applicant |
| US6289011(B1) | 2001-09-01 | Seo et al. | Applicant |
| US6298370(B1) | 2001-10-01 | Tang et al. | Applicant |
| US6307789(B1) | 2001-10-01 | Wolrich et al. | Applicant |
| US6324624(B1) | 2001-11-01 | Wolrich et al. | Applicant |
| US6345334(B1) | 2002-02-01 | Nakagawa et al. | Applicant |
| US6347344(B1) | 2002-02-01 | Baker et al. | Applicant |
| US6356962(B1) | 2002-03-01 | Kasper | Applicant |
| US6360262(B1) | 2002-03-01 | Guenthner et al. | Applicant |
| US6373848(B1) | 2002-04-01 | Allison et al. | Applicant |
| US6389449(B1) | 2002-05-01 | Nermirovsky et al. | Applicant |
| US6393483(B1) | 2002-05-01 | Latif et al. | Applicant |
| US6415338(B1) | 2002-07-01 | Habot | Applicant |
| US6426940(B1) | 2002-07-01 | Seo et al. | Applicant |
| US6427196(B1) | 2002-07-01 | Adiletta et al. | Applicant |
| US6430626(B1) | 2002-08-01 | Witkowski et al. | Applicant |
| US6434145(B1) | 2002-08-01 | Opsasnick et al. | Applicant |
| US6453404(B1) | 2002-09-01 | Bereznyi et al. | Examiner |
| US6463072(B1) | 2002-10-01 | Wolrich et al. | Applicant |
| US6532509(B1) | 2003-03-01 | Wolrich et al. | Applicant |
| US6552826(B2) | 2003-04-01 | Adler et al. | Applicant |
| US6560667(B1) | 2003-05-01 | Wolrich et al. | Applicant |
| US6577542(B2) | 2003-06-01 | Wolrich et al. | Applicant |
| US6584522(B1) | 2003-06-01 | Wolrich et al. | Applicant |
| US6587906(B2) | 2003-07-01 | Wolrich et al. | Applicant |
| US6606704(B1) | 2003-08-01 | Adiletta et al. | Applicant |
| US6625654(B1) | 2003-09-01 | Wolrich et al. | Applicant |
| US6631430(B1) | 2003-10-01 | Wolrich et al. | Applicant |
| US6631462(B1) | 2003-10-01 | Wolrich et al. | Applicant |
| US6661794(B1) | 2003-12-01 | Wolrich et al. | Applicant |
| US6667920(B2) | 2003-12-01 | Wolrich et al. | Applicant |
| US6668317(B1) | 2003-12-01 | Bernstein et al. | Applicant |
| US6681300(B2) | 2004-01-01 | Wolrich et al. | Applicant |
| US6694380(B1) | 2004-02-01 | Wolrich et al. | Applicant |
| EP379709 | 1990-08-01 | Applicant | |
| EP464715 | 1992-01-01 | Applicant | |
| EP633678 | 1995-01-01 | Applicant | |
| EP745933 | 1996-12-01 | Applicant | |
| EP809180 | 1997-11-01 | Applicant | |
| JP59111533 | 1984-06-01 | Applicant | |
| WO9415287 | 1994-07-01 | Applicant | |
| WO9738372 | 1997-10-01 | Applicant | |
| WO115718 | 2001-03-01 | Applicant | |
| WO116769 | 2001-03-01 | Applicant | |
| WO116770 | 2001-03-01 | Applicant | |
| WO116782 | 2001-03-01 | Applicant | |
| WO148596 | 2001-07-01 | Applicant | |
| WO148606 | 2001-07-01 | Applicant | |
| WO148619 | 2001-07-01 | Applicant | |
| WO150247 | 2001-07-01 | Applicant | |
| WO150679 | 2001-07-01 | Applicant |
Non-Patent Literature (27)
- U.S. Appl. No. 10/684,078, filed Oct. 10, 2003, Wolrich et al.Applicant
- U.S. Appl. No. 10/664,202, filed Sep. 16, 2003, Wolrich et al.Applicant
- U.S. Appl. No. 10/644,337, filed Aug. 20, 2003, Wolrich et al.Applicant
- U.S. Appl. No. 10/643,438, filed Aug. 19, 2003, Bernstein et al.Applicant
- U.S. Appl. No. 10/615,500, filed Jul. 8, 2003, Adiletta.Applicant
- U.S. Appl. No. 10/615,280, filed Jul. 8, 2003, Wolrich et al.Applicant
- U.S. Appl. No. 10/440,079, filed May 15, 2003, Wolrich et al.Applicant
- U.S. Appl. No. 10/208,264, filed Jul. 30, 2002, Adiletta et al.Applicant
- U.S. Appl. No. 09/476,303, filed Dec. 30, 1999, Wolrich et al.Applicant
- U.S. Appl. No. 09/475,614, filed Dec. 30, 1999, Wolrich et al.Applicant
- U.S. Appl. No. 09/473,571, filed Dec. 28, 1999, Wolrich et al.Applicant
- U.S. Appl. No. 09/387,109, filed Aug. 31, 1999, Adiletta et al.Applicant
- Byrd et al., “Multithread Processor Architectures,” IEEE Spectrum, vol. 32, No. 8, New York, Aug. 1, 1995, pp. 38-46.Applicant
- Doyle et al., Microsoft Press Computer Dictionary, 2nd ed., Microsoft Press, Redmond, Washington, USA, 1994, p. 326.Applicant
- Fillo et al., “The M-Machine Multicomputer,” IEEE Proceedings of MICRO-28, 1995, pp. 146-156.Applicant
- Gomez et al., “Efficient Multithreaded User-Space Transport for Network Computing: Design and Test of the TRAP Protocol,” Journal of Parallel and Distributed Computing, Academic Press, Duluth, Minnesota, USA, vol. 40, No. 1, Jan. 10, 1997, pp. 103-117.Applicant
- Haug et al., “Reconfigurable hardware as shared resource for parallel threads,” IEEE Symposium on FPGAs for Custom Computing Machines, 1998.Applicant
- Hauser et al., “Garp: a MIPS processor with a reconfigurable coprocessor,” Proceedings of the 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1997.Applicant
- Hyde, R., “Overview of Memory Management,” Byte, vol. 13, No. 4, 1998, pp. 219-225.Applicant
- Litch et al., “StrongARMing Portable Communications,” IEEE Micro, 1998, pp. 48-55.Applicant
- Schmidt et al., “The Performance of Alternative Threading Architectures for Parallel Communication Subsystems,” Internet Document, Online!, Nov. 13, 1998.Applicant
- Thistle et al., “A Processor Architecture for Horizon,” IEEE, 1998, pp. 35-41.Applicant
- Tremblay et al., “A Three Dimensional Register File for Superscalar Processors,” IEEE Proceedings of the 28th Annual Hawaii International Conference on System Sciences, 1995, pp. 191-201.Applicant
- Trimberger et al., “A time-multiplexed FPGA,” Proceedings of the 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1998.Applicant
- Turner et al., “Design of a High Performance Active Router,” Internet Document, Online, Mar. 18, 1999.Applicant
- Vibhatavanijt et al., “Simultaneous Multithreading-Based Routers,” Proceedings of the 2000 International Conference of Parallel Processing, Toronto, Ontario, Canada, 21-24 Aug. 2000, pp. 362-359.Applicant
- Wazlowski et al., “PRSIM-II computer and architecture,” IEEE Proceedings, Workshop on FPGAs for Custom Computing Machines, 1993.Applicant