CSC 227: Interconnection Networks and Switches

TopnotchParadox avatar
TopnotchParadox
·

Start Quiz

Study Flashcards

30 Questions

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

Expensive and impractical

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

O(1)

What is a major disadvantage of a star connected network?

Single point failure affects the whole network

What is the primary characteristic of a hybrid topology?

Integration of two or more different topologies

What is the primary advantage of a crossbar network?

Non-blocking connections

What is the cost of a crossbar of p processors?

O(p2)

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

The relative speeds of the I/O and memory buses

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

What is the primary limitation of bus-based machines?

The bandwidth of the shared bus

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

It provides a convenient broadcast media

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

What is the primary characteristic of physical topology?

It is concerned with the placement of various nodes

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.

What is the complexity of a Banyan network?

O(N log2N)

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

To ensure that packets are sorted in ascending order

What is the main advantage of a Benes network?

It is a non-blocking network

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

At most log p

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

The presence of wraparound links

What is a characteristic of a crossbar network?

It has poor cost scalability and excellent performance scalability

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

They strike a compromise between cost and performance scalability

What is the primary function of a multistage interconnection network?

To connect input devices to output devices

What is the number of stages in an Omega network?

log p stages, where p is the number of inputs/outputs

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

It has high complexity

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

Crossbar switch

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

Length of the message

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

Better use of communication resources

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

To direct packets through the network

What is the main characteristic of cut-through routing?

Dividing messages into basic units called flits

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

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

Poor use of communication resources

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.

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.

Make Your Own Quizzes and Flashcards

Convert your notes into interactive study material.

Get started for free

More Quizzes Like This

Use Quizgecko on...
Browser
Browser