CSC 227: Interconnection Networks and Switches

Communication Time Models

• Per-word transfer time (tw) includes overheads determined by message length, including bandwidth, error checking, and correction.

Store-and-Forward Routing

• A message is completely received at an intermediate hop before being forwarded to the next hop.
• Total communication cost for a message of size m words to traverse l communication links is approximated by: l \* (m \* tw + σ)

Packet Routing

• Breaks messages into packets and pipelines them through the network.
• Each packet must carry routing information, error checking, sequencing, and other related header information.
• Total communication time for packet routing is approximated by: (m / s) + l \* tw + σ

Cut-Through Routing

• Takes the concept of packet routing to an extreme by further dividing messages into basic units called flits.
• Header information must be minimized due to small flit size.

Interconnection Networks

• Switches map a fixed number of inputs to outputs.
• Cost of a switch grows as the square of the degree of the switch.
• Peripheral hardware costs grow linearly with the degree, and packaging costs grow linearly with the number of pins.

Network Topologies

• Definition: Arrangement of nodes of a computer network (physical and logical).
• Variety of network topologies have been proposed and implemented, trading off performance for cost.

Bus Topology

• Simplest and earliest parallel machines used buses.
• All processors access a common bus for exchanging data.
• Distance between any two nodes is O(1) in a bus.
• Bus provides a convenient broadcast media, but bandwidth is a major bottleneck.

Star Topology

• Every node is connected only to a common node at the center (hub).
• Distance between any pair of nodes is O(1).
• Central node becomes a bottleneck.

Hybrid Topology

• Type of network topology that integrates two or more different topologies.

Crossbars

• Use an p×m grid of switches to connect p inputs to m outputs in a non-blocking manner.
• Cost of a crossbar of p processors grows as O(p2).

Multistage Omega Network

• Example of blocking in omega network: one of the messages is blocked at a link.
• Routing in multistage omega network: an example of blocking.

Banyan Switch Fabric

• Simple banyan network with a channel graph and a 2x2 switching element.
• Perfect shuffle network requires log2N stages of N/2 switching elements.
• Complexity is on the order of N log2N.
• Collisions occur if two packets arrive at the same switch destined for the same output port.

Tagle-Sharma Switch

• Routing algorithm of Tagle-Sharma network.

Mesh Topology

• Two and three-dimensional meshes.
• Distance between any two nodes is at most log p.

Hypercubes

• Construction of hypercubes from hypercubes of lower dimension.
• Properties of hypercubes: distance between any two nodes is at most log p.
• Crossbar is a non-blocking network that allows multiple I/O connection patterns to be achieved simultaneously.