CSC 227: Interconnection Networks and Switches

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the primary limitation of broadcasting messages in a large network?

Security concerns

Hub overload

Expensive and impractical (correct)

Distance between nodes

In a star connected network, what is the distance between any pair of nodes?

O(log p)

O(p)

O(p2)

O(1) (correct)

What is a major disadvantage of a star connected network?

Single point failure affects the whole network (correct)

Easy to design and implement

High scalability

Centralized administration

What is the primary characteristic of a hybrid topology?

Integration of two or more different topologies Signup and view all the answers

What is the primary advantage of a crossbar network?

Non-blocking connections Signup and view all the answers

What is the cost of a crossbar of p processors?

O(p2) Signup and view all the answers

What is the primary factor that affects the performance of a network?

The relative speeds of the I/O and memory buses Signup and view all the answers

What is the relationship between the cost of a switch and its degree?

The cost grows as the square of the degree of the switch Signup and view all the answers

What is the primary limitation of bus-based machines?

The bandwidth of the shared bus Signup and view all the answers

What is the primary advantage of a bus in a network?

It provides a convenient broadcast media Signup and view all the answers

What is the relationship between the peripheral hardware cost and the degree of the switch?

The cost grows linearly as the degree of the switch Signup and view all the answers

What is the primary characteristic of physical topology?

It is concerned with the placement of various nodes Signup and view all the answers

What is the main difference between blocking and non-blocking networks?

Blocking networks have the property that a new connection between arbitrary unused input/output may or may not be possible, while non-blocking networks always allow it. Signup and view all the answers

What is the complexity of a Banyan network?

O(N log2N) Signup and view all the answers

What is the purpose of the perfect shuffle in a Banyan network?

To ensure that packets are sorted in ascending order Signup and view all the answers

What is the main advantage of a Benes network?

It is a non-blocking network Signup and view all the answers

What is the distance between any two nodes in a hypercube?

At most log p Signup and view all the answers

What is the main difference between a 2-D mesh with wraparound and a 2-D mesh without wraparound?

The presence of wraparound links Signup and view all the answers

What is a characteristic of a crossbar network?

It has poor cost scalability and excellent performance scalability Signup and view all the answers

What is the main advantage of multistage interconnects over crossbars and buses?

They strike a compromise between cost and performance scalability Signup and view all the answers

What is the primary function of a multistage interconnection network?

To connect input devices to output devices Signup and view all the answers

What is the number of stages in an Omega network?

log p stages, where p is the number of inputs/outputs Signup and view all the answers

What is the main disadvantage of a crossbar network in a large multiprocessor system?

It has high complexity Signup and view all the answers

What is the simplest circuit for connecting n CPUs to k memories?

Crossbar switch Signup and view all the answers

What is the primary factor that determines the per-word transfer time?

Length of the message Signup and view all the answers

What is the main advantage of packet routing over store-and-forward routing?

Better use of communication resources Signup and view all the answers

What is the purpose of the routing information in packet headers?

To direct packets through the network Signup and view all the answers

What is the main characteristic of cut-through routing?

Dividing messages into basic units called flits Signup and view all the answers

What is the total communication cost for a message of size m words to traverse l communication links in store-and-forward routing?

l * tw + m * tw Signup and view all the answers

What is the primary limitation of store-and-forward routing?

Poor use of communication resources Signup and view all the answers

Study Notes

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.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

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.