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.

This quiz assesses your understanding of interconnection networks and switches in parallel and distributed computing, including their impact on performance and cost. Topics covered include I/O and memory buses, switch degree, and peripheral hardware.