Buffered crossbar switch system

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates to a buffered crossbar switch for inter-connection between multiple modules in a communication system.

Description of the Related Art

A crossbar switch (also known as a "crosspoint switch" or a "matrix switch") interconnects a plurality of input ports and output ports to each other. A crossbar switch having P inputs and Q outputs has a switch fabric matrix with P x Q crosspoints where connections between input ports and output ports are made. Thus, packets arriving at one of the input ports might be routed to one or more specified output ports. For example, a packet might be routed to just a single specified output port (unicast), routed to all output ports (broadcast), or routed to multiple specified output ports (multicast).

Bufferless crossbar switches are frequently used in multi-processor computer systems to link processors with other resources, such as memory or other subsystems, or with internet switches or other high-performance communication networks. However, bufferless crossbar switches generally require switch fabric speedup, meaning that the internal data rate of the switch must be higher than the data rate of the link. These crossbar switches typically require high-complexity centrally-controlled scheduling algorithms to achieve 100% throughput, such as the Parallel Iterative Matching (PIM) and iSLIP algorithms.

In a buffered crossbar switch, buffers are included in the crossbar switch to temporarily store packets that cannot be routed to a specified output port instantly (i.e., blocked packets). For example, buffers might be provided for each input port, for each output port, for each crosspoint connection of the crossbar switch, or some combination thereof. Centrally-controlled scheduling algorithms might be employed to allow the input and output data streams to efficiently access the switch fabric.

<patcit id="pcit0001" dnum="US6888841B"><text>US 6,888,841</text></patcit> discloses a pipelined scheduling system for suppressing unfairness among inputs and reducing a fixed delay time. A crossbar switch connects each of the input ports to a selected one of the output ports depending on the reservation status at each time slot. <patcit id="pcit0002" dnum="EP1414252A"><text>EP 1 414 252</text></patcit> discloses a cross-point switch fabric slice.

SUMMARY OF THE INVENTION

In accordance with the invention there is provided apparatus according to claim 1.

BRIEF DESCRIPTION OF THE DRAWINGS

Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which like reference numerals identify similar or identical elements. <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> shows a block diagram of a buffered crossbar switch system operating in accordance with exemplary embodiments of the present invention;</li><li><figref idref="f0002">FIG. 2</figref> shows a block diagram of a buffered crossbar switch in accordance with an embodiment of the present invention;</li><li><figref idref="f0003">FIG. 3</figref> shows additional detail of the buffered crossbar switch of <figref idref="f0002">FIG. 2</figref>;</li><li><figref idref="f0004">FIG. 4</figref> shows another buffered crossbar switch system operating in accordance with exemplary embodiments of the present invention;</li><li><figref idref="f0005">FIG. 5</figref> shows another buffered crossbar switch system operating in accordance with exemplary embodiments of the present invention; and</li><li><figref idref="f0006">FIG. 6</figref> shows another buffered crossbar switch system operating in accordance with exemplary embodiments of the invention.</li></ul>

DETAILED DESCRIPTION

In accordance with embodiments of the present invention, a buffered crossbar switch system is provided for a high-throughput interconnection between multiple data modules in a communication system. For example, through distributed buffering and scheduling algorithms in the crossbar switch, embodiments of the present invention might be used to create concurrent virtual pipelines to interconnect multi-core processors with memory subsystems. Embodiments of the present invention might alternatively be used as, for example, client-server switches, internet routers, shared memory systems, or network switches. Embodiments of the present invention might achieve 100% throughput without speedup.

<figref idref="f0001">FIG. 1</figref> shows a block diagram of exemplary buffered crossbar switch system <b>100.</b> As shown, buffered crossbar switch system <b>100</b> comprises processing unit <b>102,</b> buffered crossbar switches <b>103</b> and <b>104,</b> and memory unit <b>105.</b> Buffered crossbar switches <b>103</b> and <b>104</b> are each in electrical communication with processing unit <b>102</b> and memory unit <b>105.</b> Thus, as shown, buffered crossbar switches <b>103</b> and <b>104</b> might be configured to implement a high-throughput interconnection between multiple data modules within processing unit <b>102</b> and memory unit <b>105.</b> In some embodiments, buffered crossbar switches <b>103</b> and <b>104</b> might be on one or more chips in communication with processing unit <b>102</b> and memory unit <b>105</b> via optical fiber.

In some embodiments, processing unit <b>102</b> might be a multi-core processor. For example, processing unit <b>102</b> might include <i>N</i> processors, where <i>N</i> is an integer greater than or equal to 1. As shown in <figref idref="f0001">FIG. 1</figref>, processing unit <b>102</b> includes processor <b>120(1),</b> processor <b>120(2),</b> and so on, through the Nth processor <b>120(<i>N</i>).</b> Processors might be, for example, implemented as general-purpose processors, such as PowerPC or ARM processors, or the processors might be, for example, implemented as accelerators for specialized functions such as digital signal processing or security protocol processing. Processing unit <b>102</b> also includes arbiter <b>122(1),</b> arbiter <b>122(2),</b> and so on, through the Nth arbiter <b>122(<i>N</i>).</b> As shown in <figref idref="f0001">FIG. 1</figref>, processor <b>120(1)</b> is in electrical communication with arbiter <b>122(1),</b> processor <b>120(2)</b> is in electrical communication with arbiter <b>122(2)</b> and so on, through processor <b>120(<i>N</i>)</b> that is in electrical communication with arbiter <b>122(N)</b>. Each of arbiters <b>122(1)</b> through <b>122(<i>N</i>)</b> has at least one input port and one output port for communication with processors <b>120(1)</b> through <b>120(<i>N</i>),</b> respectively.

In some embodiments, memory unit <b>105</b> might employ memory controllers for coordination of reading and writing operations with memory. Memory might include, for example, at least one RAM buffer. Therefore, as shown in the exemplary embodiment, memory unit <b>105</b> might include <i>M</i> memory controllers for coordination of reading information from, and writing information to, one or more RAM buffers, where <i>M</i> is an integer greater than or equal to 1. Values for <i>N</i> and <i>M</i> might be equal, but are not necessarily equal. Memory is not limited to only a RAM buffer, and might be implemented with one or more other types of memory, such as flash memory. Memory unit <b>105</b> includes memory controllers <b>152(1)</b> through memory controller <b>152(<i>M</i>).</b> Memory unit <b>105</b> also includes arbiters <b>150(1)</b> through arbiter <b>150(<i>M</i>).</b> As shown in <figref idref="f0001">FIG. 1</figref>, memory controller <b>152(1)</b> is in electrical communication with arbiter <b>150(1),</b> memory controller <b>152(2)</b> is in electrical communication with arbiter <b>150(2),</b> and so on, through memory controller <b>152(<i>M</i>)</b> that is in electrical communication with arbiter <b>150(<i>M</i>).</b> Each of arbiters <b>150(1)</b> through <b>150(<i>M</i>)</b> has at least one input port and one output port for communication with memory controllers <b>152(1)</b> through <b>152(<i>M</i>),</b> respectively. Embodiments of the present invention might alternatively include a centralized arbiter for output arbitration. Other embodiments of the present invention might include a combination of localized and centralized arbiters.

Buffered crossbar switches <b>103</b> and <b>104</b> include a switch fabric configured to allow any input to the switch to be transferred to any one or more outputs of the switch. In exemplary embodiments, buffered crossbar switch <b>103</b> has <i>N</i> input ports and <i>M</i> output ports, and buffered crossbar switch <b>104</b> has <i>M</i> input ports and <i>N</i> output ports, where <i>N</i> is the number of processors and <i>M</i> is the number of memory controllers. As shown in <figref idref="f0001">FIG. 1</figref>, buffered crossbar switch <b>103</b> has <i>N</i> input ports, shown as <b>132(1)</b> through 132(<i>N</i>), and <i>M</i> output ports, shown as <b>138(1)</b> through <b>138(<i>M</i>),</b> Buffered crossbar switch <b>104</b> has <i>M</i> input ports, shown as <b>148(1)</b> through <b>148(<i>M</i>),</b> and <i>N</i> output ports, shown as <b>142(1)</b> through <b>142(<i>N</i>).</b> While two buffered crossbar switches are shown in <figref idref="f0001">FIG. 1</figref>, the present invention is not so limited, and, thus, buffered crossbar switch system <b>100</b> might include up to <i>B</i> buffered crossbar switches, where <i>B</i> is an integer greater than or equal to 1.

For example, an exemplary embodiment of the present invention, such as shown in <figref idref="f0006">FIG. 6</figref>, might include 5 buffered crossbar switches: one switch (shown as buffered crossbar switch <b>602</b>) to send addresses from processing unit <b>102</b> to memory unit <b>105,</b> one switch (shown as buffered crossbar switch <b>604</b>) to send data from processing unit <b>102</b> to memory unit <b>105,</b> one switch (shown as buffered crossbar switch <b>606</b>) to send addresses from memory unit <b>105</b> to processing unit <b>102,</b> one switch (shown as buffered crossbar switch <b>608</b>) to send data from memory unit <b>105</b> to processing unit <b>102,</b> and one switch (shown as buffered crossbar switch <b>610</b>) to send responses from the memory to the processors.

As shown in <figref idref="f0001">FIG. 1</figref>, buffered crossbar switch <b>103</b> is configured to switch data sent from processing unit <b>102</b> to memory unit <b>105,</b> and buffered crossbar switch <b>104</b> is configured to switch data sent from memory unit <b>105</b> to processing unit <b>102.</b> Thus, buffered crossbar switches <b>103</b> and <b>104</b> might be used to set which ones of <i>N</i> processors of processing unit <b>102</b> are in communication with which ones of the <i>M</i> memory controllers of memory unit <b>105.</b> For example, data provided from processor <b>120(1)</b> of processing unit <b>102</b> might be provided to input port <b>132(1)</b> of buffered crossbar switch <b>103.</b> Arbiter <b>122(1)</b> controls what data processor <b>120(1)</b> provides to input port <b>132(1)</b> of buffered crossbar switch <b>103.</b> As indicated by dashed arrow <b>134,</b> buffered crossbar switch <b>103</b> might be configured to provide this data to output port <b>138(2)</b> of buffered crossbar switch <b>103.</b> Arbiter <b>150(2)</b> controls which crosspoint buffer is transferred to output port <b>138(2)</b> of buffered crossbar switch <b>103.</b> Thus, buffered crossbar switch <b>103</b> provides this data to memory controller <b>152(2)</b> of memory unit <b>105.</b> Analogously, dashed arrows <b>135</b> and <b>136</b> indicate other exemplary data path settings of buffered crossbar switch <b>103.</b> Buffered crossbar switch <b>103</b> might also be set to provide the data from one input port to multiple output ports. Similarly, data from memory controller <b>152(1)</b> of memory unit <b>105</b> might be provided to buffered crossbar switch <b>104</b> at input port <b>148(2).</b> Arbiter <b>150(1)</b> controls what data memory controller <b>152(1)</b> provides to input port <b>148(2)</b> of buffered crossbar switch <b>104.</b> As indicated by dashed arrow <b>145,</b> buffered crossbar switch <b>104</b> might be set to provide this data to one output, in this instance, output port <b>142(2),</b> which provides the data to processor <b>120(2)</b> of processing unit <b>102.</b> Arbiter <b>122(2)</b> controls which crosspoint buffer is transferred to output port <b>142(2)</b> of buffered crossbar switch <b>104.</b> Analogously, dashed arrows <b>144</b> and <b>146</b> indicate other exemplary data path settings of buffered crossbar switch <b>104.</b>

<figref idref="f0002">FIG. 2</figref> shows a block diagram of buffered crossbar switch system <b>200</b> in accordance with an embodiment of the present invention. As shown, buffered crossbar switch system <b>200</b> includes buffered crossbar switch <b>226</b> and virtual output queues (VOQs) <b>202, 204</b> and <b>206.</b> Buffered crossbar switch <b>226</b> has 3 input ports, shown as input ports <b>220, 222</b> and <b>224,</b> and 3 output ports, shown as output ports <b>246, 248</b> and <b>250.</b> Thus, as shown in <figref idref="f0002">FIG. 2</figref>, <i>N</i> = <i>M</i> = 3. Input port <b>220</b> is in electrical communication with VOQ <b>202,</b> input port <b>222</b> is in electrical communication with VOQ <b>204</b> and input port <b>224</b> is in electrical communication with VOQ <b>206.</b> Output port <b>246</b> is in electrical communication with output queue 1 <b>252,</b> output port <b>248</b> is in electrical communication with output queue 2 <b>254</b> and output port <b>250</b> is in electrical communication with output queue M <b>256.</b> Some embodiments of the present invention might not include output queues <b>252, 254</b> and <b>256.</b> Buffered crossbar switch <b>226</b> includes a FIFO buffer at each crosspoint of the 3 x 3 switch matrix. Thus, in exemplary embodiments, an <i>N</i> x <i>M</i> switch will have <i>N</i> x <i>M</i> buffers. These FIFO buffers are shown in <figref idref="f0002">FIG. 2</figref> as crosspoint queues <b>228, 230, 232, 234, 236, 238, 240, 242</b> and <b>244.</b> Crosspoint queues temporarily store data before forwarding the data to the respective output port. Crosspoint queues allow the switch fabric to receive data nearly simultaneously at multiple input ports without blocking.

VOQs <b>202, 204</b> and <b>206</b> might each include one or more virtual first-in, first-out (FIFO) buffers. For example, VOQ <b>202</b> might include three FIFOs, shown in <figref idref="f0002">FIG. 2</figref> as FIFOs <b>202a, 202b</b> and <b>202c;</b> however, the present invention is not so limited and more or less FIFOs might be employed. Each VOQ buffer is in electrical communication with an arbiter that schedules access by the VOQs to the switch fabric of buffered crossbar switch <b>226.</b> As shown in <figref idref="f0002">FIG. 2</figref>, VOQ <b>202</b> is in electrical communication with arbiter <b>214,</b> VOQ <b>204</b> is in electrical communication with arbiter <b>216</b> and VOQ <b>206</b> is in electrical communication with arbiter <b>218.</b> Although shown in <figref idref="f0002">FIG. 2</figref> as VOQs, embodiments of the present invention might employ other types of input buffering.

Packets sent to VOQs <b>202, 204</b> and <b>206</b> are sorted in FIFOs according to the destination addresses of the packets. Packets generally are of a variable length, thus, embodiments of the present invention segment packets into "cells" before they are provided to the switch fabric. A cell is a fixed number of bits such that packets of varying sizes might be segmented into a number of cells of fixed size, plus padding, if necessary. Crosspoint queues temporarily store data cells before cells are transferred to corresponding output queue(s). Each crosspoint queue is in electrical communication with an arbiter that schedules access by the crosspoint queues to the output ports of buffered crossbar switch <b>226.</b> As shown, crosspoint queues <b>228, 230</b> and <b>232</b> are in electrical communication with arbiter <b>225,</b> crosspoint queues <b>234, 236</b> and <b>238</b> are in electrical communication with arbiter <b>227</b> and crosspoint queues <b>240, 242</b> and <b>244</b> are in electrical communication with arbiter <b>229.</b> Referring back to <figref idref="f0001">FIG. 1</figref>, arbiters <b>214, 216,</b> and <b>218</b> correspond to arbiters <b>122(1)</b> through <b>122(<i>N</i>)</b> and arbiters <b>225, 227</b> and <b>229</b> correspond to arbiters <b>150(1)</b> through <b>150(<i>M</i>)</b> where <i>N</i> = <i>M</i> = 3.

Some embodiments of the present invention include output queues <b>252, 254</b> and <b>256</b> to reassemble data cells into packets. Output queues <b>252, 254</b> and <b>256</b> are not needed in embodiments that send packets directly to the switch fabric (i.e. do not segment packets into cells) because no packet reassembly is required.

Some embodiments of the present invention provide that the size of each crosspoint queue (e.g. queue depth) might be variable. Thus, the depth of each crosspoint queue might vary based on, for example, the round-trip time of data transfer through buffered crossbar switches <b>103</b> and <b>104</b> of <figref idref="f0001">FIG. 1</figref>. For example, a data path having a long round-trip time might require a larger crosspoint buffer to store data cells during the round-trip transfer of the packet. Thus, embodiments of the present invention provide crosspoint queues of varying depths to support different round-trip times.

Round-trip time is the time required for a credit to return to the input arbiter and the time required to send data to a crosspoint buffer. Initially, all crosspoint buffers are empty. Each input arbiter of the buffered crossbar switch might track how many credits are available for each crosspoint buffer. For example, the number of credits, <i>C</i>, available for each input port <i>i</i> at crosspoint buffer <i>i, j</i> might be represented as <i>C(i, j).</i> The number of credits might initially be equal to the depth of crosspoint buffer <i>i, j.</i> For each data cell sent to crosspoint buffer <i>i, j</i> from input port <i>i</i>, the number of credits, <i>C</i>, is decremented. When <i>C</i>(<i>i</i>, <i>j</i>) is zero, input port <i>i</i> must stop sending data cells, or else crosspoint buffer <i>i, j</i> will overflow. When the output arbiter at output <i>j</i> pulls a cell from crosspoint buffer (<i>i, j), C</i>(<i>i, j)</i> is incremented ("returning a credit"). For example, in a system where it takes two cycles for an input to write to a crosspoint buffer and three cycles to return a credit, the round-trip time is 5 cycles. With a deeper crosspoint buffer, the input can keep sending cells into the crosspoint buffer without exhausting its credits. In exemplary embodiments of the present invention, the depth of the crosspoint buffer might increase as credit return latency, and thus round-trip time, increases.

Input arbiters <b>214, 216</b> and <b>218</b> are distributed arbiters because each of N input FIFO buffers <b>202, 204</b> and <b>206</b> has one arbiter. Input arbiters are not in electrical communication with each other, thus facilitating scalability of buffered crossbar switch <b>226,</b> since distributed arbiters might have a smaller physical size than a centralized arbiter. Similarly, output arbiters <b>225, 227</b> and <b>229</b> are also distributed arbiters because each of the <i>M</i> output queues <b>252, 254</b> and <b>256</b> has one arbiter.

Arbiters <b>214, 216, 218, 225, 227 and 229</b> are, for exemplary embodiments, implemented as "round-robin" schedulers implementing a round-robin algorithm: buffers are processed in ascending or descending order, and the process returns to the first buffer in the sequence after the last buffer in the sequence is served. For example, as each one of non-empty VOQs <b>202a, 202b</b> and <b>202c</b> is served by arbiter <b>214,</b> data cells in the serviced buffer are provided to the switch fabric until the currently serviced VOQ becomes empty or the timeslot for the VOQ is over. Either such occurrence causes arbiter <b>214</b> to advance to the next VOQ in the sequence. Arbiter <b>214</b> skips empty VOQs to serve the next non-empty VOQ. Arbiters <b>216, 218, 225, 227</b> and <b>229</b> operate similarly as arbiter <b>214.</b> Although a round-robin scheduling algorithm is described, the present invention is not so limited, and other scheduling algorithms might be employed, for example longest queue first scheduling wherein the queue that has held data for the longest time is given scheduling priority. Further, embodiments of the present invention provide input and output arbiters that do not necessarily employ the same scheduling algorithm and a combination of scheduling algorithms might be employed.

Generally, arbitration is performed as described above. Thus, if buffered crossbar switch <b>226</b> has an equal number, <i>N</i>, of inputs and outputs, a packet consisting of <i>Z</i> cells, where <i>Z</i> is an integer, might take <i>N</i> x <i>Z</i> clock cycles to reach the destination output queue. Exemplary embodiments of the present invention provide for cell prioritization. For example, priority might be assigned on a processor basis, wherein certain processors within processing unit <b>102</b> might be assigned higher priority than other processors, such that the associated arbiter would deliver all <i>Z</i> cells of a packet consecutively in <i>Z</i> cycles. Alternatively, priority might be assigned on a packet basis, wherein, for example, certain types of packets might be assigned higher priority than other types of packets.

Non-uniform output occurs with repeated access of a particular output port of buffered crossbar switch <b>226.</b> Non-uniform output might limit the maximum throughput of buffered crossbar switch <b>226</b> since access to the output port is controlled by the output arbiter. For example, as shown in <figref idref="f0001">FIG. 1</figref>, each output port of buffered crossbar switch <b>226</b> corresponds to particular memory controller within memory unit <b>105.</b> Typically, data transfer of a block of memory having sequential addresses is managed by one memory controller. The destination memory address determines which output of the buffered crossbar switch <b>226</b> is accessed. Thus, sequential memory accesses might cause a non-uniform output condition to arise, which might limit the maximum throughput of buffered crossbar switch <b>226.</b> Some embodiments of the present invention scramble memory addresses before passing data for such addresses through buffered crossbar switch <b>226.</b> Scrambling of memory addresses translates sequential memory accesses into accesses having a more uniform distribution of output port accesses.

<figref idref="f0003">FIG. 3</figref> shows additional detail of the buffered crossbar switch system of <figref idref="f0002">FIG. 2</figref>. As shown in <figref idref="f0003">FIG. 3</figref>, exemplary embodiments of buffered crossbar switch <b>301</b> additionally include <i>M</i> multiplexers, shown as <b>302, 304</b> and <b>306,</b> where <i>M</i> is the number of outputs of the crossbar switch. As shown in <figref idref="f0003">FIG. <i>3</i></figref><i>, N= M=</i> 3. For a switch having <i>N</i> inputs and <i>M</i> outputs, the switch fabric of buffered crossbar switch <b>301</b> might include <i>M "N-</i>to<i>-</i>1" multiplexers. As shown, arbiter <b>225</b> and crosspoint queues <b>228, 230</b> and <b>232</b> are in electrical communication with multiplexer <b>302.</b> Arbiter <b>225</b> controls which of the crosspoint queues is asserted by multiplexer <b>302</b> to output port <b>246,</b> thus accessing output queue <b>252.</b> Similarly, crosspoint queues <b>234, 236</b> and <b>238</b> are in electrical communication with multiplexer <b>304.</b> Arbiter <b>227</b> controls which of the crosspoint queues is asserted by multiplexer <b>304</b> to output port <b>248,</b> thus accessing output queue <b>254.</b> Crosspoint queues <b>240, 242</b> and <b>244</b> are in electrical communication with multiplexer <b>306.</b> Arbiter <b>229</b> controls which of the crosspoint queues is asserted by multiplexer <b>306</b> to output port <b>250,</b> thus accessing output queue <b>256.</b>

While described above as being implemented as a monolithic chip, the present invention is not so limited. For example, as shown in <figref idref="f0004">FIG. 4</figref>, each buffered crossbar switch might occupy its own circuit board, shown as switch cards <b>406(1)</b> through <b>406(<i>L</i>).</b> Multiple switch cards might occupy a shelf, with multiple shelves, shown as shelves <b>404(1)</b> through <b>404(<i>K</i>),</b> forming switch chassis <b>400.</b> Similarly, the processors and memories might be located on line chassis <b>402.</b> Line chassis <b>402</b> might include multiple shelves, shown as shelves <b>409(1)</b> through <b>409(<i>K</i>),</b> each shelf including multiple line cards, shown as line cards <b>410(1)</b> through <b>410(<i>L</i>).</b> Each line card might contain devices, such as memory or processors, which communicate via the switch cards. A line chassis typically communicates with a switch chassis via electrical cables or optical links, shown as links <b>412, 414, 416</b> and <b>418.</b>

<figref idref="f0005">FIG. 5</figref> shows another buffered crossbar switch system operating in accordance with exemplary embodiments of the present invention. As shown in <figref idref="f0005">FIG. 5</figref>, one or more buffered crossbar switches, shown as <b>500,</b> might be used to make a chain of processors <b>102</b> and storage modules <b>105</b> where a storage module might serve as a buffer for two processors to communicate with each other. Buffered crossbar switches <b>500</b> operate as described with regard to <figref idref="f0001">FIG. 1</figref>. Buffered crossbar switches <b>500</b> might also be in electrical communication with bridge <b>502,</b> thus, creating a branch along the chain. Bridge <b>500</b> might have one high-bandwidth port for communication with buffered crossbar switches <b>500,</b> and lower bandwidth ports for communication with slower or legacy data modules, shown as processor <b>504</b> and storage modules <b>506</b> and <b>508.</b> Thus, embodiments of the present invention provide a way for slower data modules to communicate with faster data modules without limiting the system bandwidth available to the faster data modules. Bridge <b>502</b> might employ buffered crossbar switches as described above, or might employ a design that doesn't use buffered crossbar switches.

It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the scope of the invention as expressed in the following claims.

Reference herein to "one embodiment" or "an embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase "in one embodiment" in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments necessarily mutually exclusive of other embodiments. The same applies to the term "implementation."

While the exemplary embodiments of the present invention have been described with respect to processes of circuits, including possible implementation as a single integrated circuit, a multi-chip module, a single card, or a multi-card circuit pack, the present invention is not so limited. As would be apparent to one skilled in the art, various functions of circuit elements may also be implemented as processing blocks in a software program. Such software may be employed in, for example, a digital signal processor, micro-controller, or general purpose computer.

The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as magnetic recording media, optical recording media, solid state memory, floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium or carrier, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits. The present invention can also be embodied in the form of a bitstream or other sequence of signal values electrically or optically transmitted through a medium, stored magnetic-field variations in a magnetic recording medium, etc., generated using a method and/or an apparatus of the present invention.

A method of transferring data between data modules, is preferably provided, each of said data modules being at least one of a data processing module and a data storage module, the method comprising: passing the data through at least one crossbar switch, wherein input nodes and output nodes of each of the crossbar switches are coupled to corresponding ones of the data modules, the ith crossbar switch having an Ni-input node by Mi-output node switch fabric, wherein Ni and Mi are each positive integers greater than one and wherein each crossbar switch comprises: reading, from an input buffer at each input node having an input arbiter, data packets from each input buffer in accordance with a first scheduling algorithm; reading, from an output arbiter of a crosspoint buffer at each crosspoint of the switch fabric, the crosspoint buffer having a queue with an output arbiter, data packets from the crosspoint buffer queue in accordance with a second scheduling algorithm; and receiving, at an output node, segments of data packets from one or more corresponding crosspoint buffers.

The method may further comprise varying, for each crosspoint buffer queue a depth of the queue in accordance with a round-trip time of data transfer through one of the at least one crossbar switch.

The method may further comprise scrambling, when a data storage module employs sequential addressing of locations in memory, addresses of the locations in memory before passing the data through the at least one crossbar switch.

The method may further comprise partitioning the packet of data provided to the input buffer into equal length cells.

A machine-readable storage medium is preferably provided, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method for transferring data between data modules, each of said data modules being at least one of a data processing module and a data storage module, comprising the steps of: passing the data through at least one crossbar switch, wherein input nodes and output nodes of each of the crossbar switches are coupled to corresponding ones of the data modules, the ith crossbar switch having an Ni-input node by Mi-output node switch fabric, wherein Ni and Mi are each positive integers greater than one and wherein each crossbar switch comprises: reading, from an input buffer at each input node having an input arbiter, data packets from each input buffer in accordance with a first scheduling algorithm; reading, from an output arbiter of a crosspoint buffer at each crosspoint of the switch fabric, the crosspoint buffer having a queue with an output arbiter, data packets from the crosspoint buffer queue in accordance with a second scheduling algorithm; and receiving, at an output node, segments of data packets from one or more corresponding crosspoint buffers.

It should be understood that the steps of the exemplary methods set forth herein are not necessarily required to be performed in the order described, and the order of the steps of such methods should be understood to be merely exemplary. Likewise, additional steps may be included in such methods, and certain steps may be omitted or combined, in methods consistent with various embodiments of the present invention.

As used herein in reference to an element and a standard, the term "compatible" means that the element communicates with other elements in a manner wholly or partially specified by the standard, and would be recognized by other elements as sufficiently capable of communicating with the other elements in the manner specified by the standard. The compatible element does not need to operate internally in a manner specified by the standard.

Also for purposes of this description, the terms "couple," "coupling," "coupled," "electrical communication," "connect," "connecting," or "connected" refer to any manner known in the art or later developed in which energy is allowed to be transferred between two or more elements, and the interposition of one or more additional elements is contemplated, although not required. Conversely, the terms "directly coupled," "directly connected," etc., imply the absence of such additional elements. Signals and corresponding nodes or ports may be referred to by the same name and are interchangeable for purposes here.