# Presentation: 482442

## Some Observations Regarding the Future of High-Performance Interconnects

- José Duato

*Technical University of Valencia*
*Valencia, Spain*

- Communication Architecture for Clusters, Rhodos, 2006

## Outline

- Convergence or radical departure?
- Toward cost-effectiveness
- A simple performance model
- Congestion and HOL blocking
- Traditional solutions
- Dynamic evolution of congestion trees
- A different approach: RECN
- Performance evaluation
- Conclusions

## Convergence or radical departure?

- During the last decade, clusters and even supercomputers benefited from commodity components
- Same processors, usually with larger cache
- Same memory, usually with SECDED
- Same disks, usually with higher capacity
- Same interconnects, except for very high performance
- The I/O bus was the main bottleneck in server systems
- PCI-Express provided performance and scalability
- Introduced in the desktop market, but not really needed!
- Convergence between the desktop, datacenter and supercomputing markets?

## Convergence or radical departure?

- Single-core processors limited by heat dissipation
- Multi-core chips are more efficient
- Eight cores at half the voltage and frequency deliver 4X computing speed for the same (?) power consumption
- Simple in-order cores increase efficiency
- Lower clock frequency reduces memory wall problem
- Will multi-core chips succeed in desktop market?
- Legacy applications may use only one core
- Most programmers not familiar with parallel software
- Multi-core chips suitable for the server market
- Implicit parallelism (tasks from many users)
- A large number of simple cores increases efficiency

## Convergence or radical departure?

- Unless programmers switch to parallel software
- Very different processing chips will be used for desktop computers and datacenters/supercomputers (T1, Cell)
- Will the PS3 help to convince software companies?
- Current servers already represent a radical departure from desktop commodity components
- Specialized form factor
- Need for much higher availability
- Single system image through system software
- Yet, high-performance network interfaces still link to the current standard I/O interconnect
- Both InfiniBand and Advanced Switching intended to be directly attached to the memory controller

## Convergence or radical departure?

- Future servers may represent an even more radical departure
- Trend toward outsourcing IT services
- Very strict security requirements
- Solutions based on partitioning and virtualization
- Providing performance guarantees in virtual servers requires some kind of quality of service support
- This situation may be aggravated by the trend toward merging all the current interconnects (interprocessor, SAN, LAN) into a single one

## Toward cost-effectiveness

- Standard-based switched interconnects
- The result of the combined interest of several companies
- Introduce overheads (e.g. network management) and constraints (e.g. in-order delivery)
- Plug into standard I/O interconnects, thus extra delay
- Average working point closer to saturation
- Links consume roughly the same regardless of utilization, so better keep them doing something useful
- Smaller number of components reduces cost and power consumption, driving network closer to saturation
- CMPs increase communication needs w.r.t. single-core
- Partitioning and virtualization in a unified interconnect will lead to a higher degree of sharing and utilization

- Problem: Network Throughput beyond Saturation

## The old performance metrics

- Latency
- Increased by:
- Going through NB plus I/O interconnect plus NIC
- Loss of fine-grain pipelining through I/O link and NIC
- Software overhead
- Sweet old 80s
- On-chip switch and links (e.g. iWarp, INMOS transputer)
- Special instructions and/or registers to access the network
- Only way to implement true zero-copy (from ALU to ALU)
- Throughput
- Links and topology define the raw bandwidth, reduced by encoding and protocol overhead
- Routing may try to balance link and path utilization
- Congestion control prevents degradation on saturation

## Base latency is easy to compute but throughput is difficult to estimate
The network can be considered as a pipe of variable width

Three points of interest:
Injection point
Narrowest section in the pipe
Delivery point
The narrowest section determines throughput

- The network can be considered as a pipe of variable width
- Three points of interest:
- Injection point
- Narrowest section in the pipe
- Delivery point
- The narrowest section determines throughput

- A simple performance model (throughput)

- Injection
- bandwidth

- Bisection
- bandwidth

- Delivery
- bandwidth

## A simple performance model (throughput)

- Transmission
- time

- Sending
- overhead

## A simple performance model (throughput)

- Network
- injection

- Network
- reception

- More bandwidth is required at reception side (e.g. BlueGene)
- Indirect networks do not fulfill this requirement

## A simple performance model (throughput)

-   is the fraction of traffic that crosses the network bisection
-   is the network efficiency, and mostly depends on link efficiency, routing efficiency, and switch efficiency

## Congestion and HOL blocking

- Throughput
- Links and topology define the raw bandwidth, reduced by protocol overhead (control fields)
- Routing may try to balance link and path utilization
- Congestion control prevents degradation on saturation
- Partitioning and virtualization
- Physical partitioning will no longer be feasible with CMPs: multiple cores will share a link
- Providing performance guarantees will require stable performance
- Congestion control will become mandatory in future systems

## Congestion trees and HOL blocking

- Several packets request the same output port
- One makes progress, the others wait
- Congestion:
- Persistent contention
- It is quickly propagated by flow control (lossless nets), forming **congestion trees**
- Network performance degrades **dramatically!!!**

- Head of line (HOL) blocking:
- When the first packet in a queue is blocked, any other packet in the same queue is also blocked, even if it will request available resources

- WHY?

## Traditional Solution

- Overdimensioning the network

## Congestion trees

- Network
- contention

## Congestion trees

**Persistent**
**network**
**contention**

## Congestion trees

**Persistent**
**network**
**contention**

**Flow control**

## Congestion trees

**Persistent**
**network**
**contention**

**Congestion**
**propagates**

## Congestion trees

- Congestion
- tree root

- Congestion
- tree leaf

- Congestion
- tree leaf

- Congestion
- tree branch

- Congestion
- tree branch

## Traditional view of congestion trees

- Traditional ideas about congestion trees evolution:
**Congestion propagates from the root to the leaves**
**Congestion first appears at egress sides**
**Congestion vanishes from leaves to root**

## Different dynamics of congestion trees

- Effect of switch architecture (I):
**Switch speedup may vary for different technologies**
**Depending on switch speedup, congestion may appear at ingress or egress sides**

## Different dynamics of congestion trees

- Effect of switch architecture (II):
**Several congested points may appear both at ingress or egress sides along the branches of a congestion tree**

## Different dynamics of congestion trees

- Impact of traffic patterns (I):
**Depending on traffic patterns, the congestion tree root may “move” downstream**

- Switch speedup: 2
- Solid flows appear first, dashed ones later

## Different dynamics of congestion trees

- Impact of traffic patterns (II):
**Different congestion trees may merge, even when the involved packets have different destinations**

- Switch speedup: 2
- Solid flows appear first, dashed ones later

## Different dynamics of congestion trees

- Impact of traffic patterns (III):
**Different congestion trees may overlap without merging**

- Switch speedup: 2
- Solid flows appear first, dashed ones later

## Different dynamics of congestion trees

- Impact of traffic patterns (IV):
**A congestion tree root may also move upstream**

- Switch speedup: 2
- dashed flow disappears first

## Congestion trees and HOL blocking

-   Congestion trees introduce HOL blocking, and this degrades network performance dramatically

## Why Old Techniques Are not Suitable?

- Proactive Congestion Management (congestion prevention)
- Path setup before data transmission
- Used in ATM, computer networks (QoS)
***High overhead, high latencies (not suitable for HPC)***

- The real problem is not the congestion,
- but its negative effects (HOL blocking)

- Reactive Congestion Management (congestion recovery)
- Injection limitation techniques using closed-loop feedback
***Do not scale with network size and link bandwidth***
- Notification delay (proportional to distance)
- Link capacity (proportional to clock frequency)
- May produce network instabilities

## Why Old Techniques Are not Suitable?

- HOL blocking elimination/reduction
- DAMQs and Virtual Channels
- Different buffers for different flows
***Not efficient for multihop networks***

- VOQ (Virtual Output Queueing)
- VOQ at switch level:A separate queue at every input port for every output port
-  ***Scales but does not eliminate HOL blocking completely***
- VOQ at network level: A separate queue at every input port for every destination
***Number of required resources grows at least quadratically with network size !!!***

- Credit Flow Controlled ATM
- References congestion to network output only
- A separate queue at every output port for every destination
***Consumes a large number of buffers***

**Notes:**
In general, these techniques try to separate different flows of packets in order to avoid HOL blocking

## RECN: Regional Explicit Congestion Notification

- RECN is a new efficient and scalable congestion management technique
- Basic ideas:
- The real problem is not the congestion, but its negative effects (HOL blocking)
- By eliminating HOL blocking, congestion becomes harmless
- Non-congested flows do not introduce significant HOL blocking
- HOL blocking elimination:
- Congestion trees are exactly identified
- Packets belonging to congested flows are stored in specific Set Aside Queues (SAQs)
- Packets belonging to non-congested flows are stored in a “common” queue
- Implementation requirements:
- Deterministic source routing
- A reduced number of SAQs per port, controlled by a CAM

## How RECN works

- RECN basic procedure:
- Congested points are detected at any input or output switch port of the network
- The routes to detected congested points are progressively notified to input and output ports crossed by congested flows
- After receiving a notification, a port dynamically allocates a SAQ for the detected congested point
- A packet arriving at a port will be stored in a SAQ if it will pass through the congested point associated to that SAQ
- A packet arriving at a port will be stored in the common (“cold”) queue if its route does not match any SAQ
- SAQs can be dynamically deallocated, and later allocated for other congested points

## How RECN Works

- A congestion point forms

## How RECN Works

- Cold queue fills over
- a threshold

## How RECN Works

## How RECN Works

- Internal notification to each
- input port
- sending packets to
- the output port

## How RECN Works

## How RECN Works

- Input ports allocate
- a new SAQ for
- packets addressed to
- the congested output port

## How RECN Works

## How RECN Works

- Notification sent when
- the SAQ fills
- over a threshold

## How RECN Works

## How RECN Works

- A new SAQ allocated
- for the congested port
- at each output port

## How RECN Works

- Internal notification
- when the SAQ fills over
- A threshold

## How RECN Works

- The input port allocates
- A new SAQ

## How RECN Works

- At the end, the congestion
- tree builds and it is stored
- entirely in SAQs

## RECN assumptions: Turnpools

- 0

- 1

- 2

- 3

- 4

- 5

- 6

- 7

- 3

- 7

- turn pool

- t. pointer

- D

- Direction bit

- Turn example

- 31 bits

- AS packet header

## RECN assumptions: Switch Model

- XBAR

- . . .

- . . .

- RAM
- out

- Arbiter

- . . .

- . . .

- . . .

- Dynamic queue
- management

- Dynamic queue
- management

- LC

- LC

- LC

- LC

- LC

- LC

- CAM

- RAM
- out

- CAM

- RAM
- out

- CAM

- RAM
- in

- CAM

- RAM
- in

- CAM

- RAM
- in

- CAM

- RECN assumptions: RAM and CAM structure

- RECN assumptions: Flow Control

- Two different and simultaneous FCs:
- Generic Credit-Based flow control for the whole RAM
- No packet is sent from the upstream output port if no credits are available
- SAQ Specific Xon/Xoff flow control
- Follows the Stop & Go model
- Only between adjacents SAQ allocated for the same congestion tree
- Avoids a “hot flow” filling completely the port RAM
- Included in AS standards

## RECN details

- Congestion Detection (Outputs):
- Cold Queue fills over Detection Threshold (Xoff Threshold)
- Congested point: output port
- SAQs are not allocated at the output port

## RECN details

- Congestion Detection (Inputs):
- A Detection Queue fills over Detection Threshold (Xoff Threshold)
- Congested point: output port associated to this Detection Queue
- A SAQ is allocated at the input port

## RECN details

- Actions after Detection:
- If output detection:
- Congestion is notified to input ports sending packets to congested ports
- Notification includes turnpool information and mask bits
- Upon notification reception, an input port must allocate a SAQ

- If input detection:
- A SAQ is immediately allocated at the input port
- Detection Queue and allocated SAQ are swapped

- Packets

- Notifications

## RECN details

- Primary SAQ allocation :
- A new SAQ is allocated at an input port for a congested output port
- The corresponding CAM line fields must be filled

- +4

## RECN details

- Reception of packets after input SAQ allocation (Example 1):

- 4

- 4

- 6

- 4

- 4

- +4

- ...000045

- ...000004

- ..0111111

- ..0000111

- SAQ 0

- ?

- +4

## RECN details

- Reception of packets after input SAQ allocation (Example 2):

- 7

- 9

- 2

- 4

- 4

- ...000045

- ...000004

- ..0111111

- ..0000111

- Detection
- Queue

- ?

- +7

## RECN details

- Congestion information propagation:
- When the occupancy of an input SAQ reaches the Xoff threshold, congestion information must be propagated to the next switch
- A flow control packet including turnpool and the number of set mask bits is sent upstream

- +4

- .....00004

- 3

- turnpool

- # of set bits

## RECN details

- RECN Flow Control Packet Format for Advanced Switching
- Transaction Layer Packet (Protocol Interface 7)
- 8 bytes length (2 AS Dwords)

- FC type specifies if Xon or Xoff packet
- Packet Type must be set to 0 (reserved for RECN)
- Header CRC, Traffic Class and Ordered Only (oo) fields are required by other AS features

## RECN details

- Actions upon reception of a flow control packet:
- The received turnpool is compared to those of active SAQs at the output port
- When matching, the packet is just a FC packet (a SAQ is affected)
- If not, the packet produces a new SAQ allocation

- +4

- .....00004

- 3

- turnpool

- # of set bits

- SAQ 0

- SAQ 1

- SAQ n

- CAM line SAQ 0

- CAM line SAQ 1

- CAM line SAQ n

- Cold Queue

- .....00025

- ....0111111

- .....00004

- ...0000111

- ¡¡ No matching!!

## RECN details

- Output SAQ allocation :
- A new SAQ is allocated at an output port for a congested point at other switch
- The corresponding CAM line fields must be filled with the notified turnpool and number of set mask bits
- Output SAQs also propagate congestion information when filled

- +4

- SAQ 0

- SAQ 1 (newly allocated)

- SAQ n

- CAM line SAQ 0

- CAM line SAQ 1

- CAM line SAQ n

- Cold Queue

## RECN details

- SAQ deallocation :
- A SAQ is deallocated only when:
- It is empty and,
- It is not blocked and,
- It is not in Xoff state
- If these conditions are met, congestion is not present at the SAQ port
- A SAQ does not depend on other SAQs for being deallocated, so the deallocation process is completely distributed
- The deallocation process does not require control messages
- A deallocated SAQ can be reallocated for other congestion tree

## RECN Performance

- Network throughput - Corner case 1, 64x64 BMIN

## RECN Performance

- Network throughput - Corner case 2, 64x64 BMIN

## RECN Performance

- Network throughput – Traces, 64x64 BMIN

- Compression Factor set to 20

- Compression Factor set to 40

## RECN Performance

- SAQ utilization – Corner Case 1, 64x64 BMIN

- Maximum # SAQs used (ingress)

- Maximum # SAQs used (egress)

- Total # of active SAQS

## RECN Performance

- SAQ utilization – Corner Case 2, 64x64 BMIN

- Maximum # SAQs used (ingress)

- Maximum # SAQs used (egress)

- Total # of active SAQS

## RECN Performance

- SAQ utilization – Traces, Comp. Factor 20, 64x64 BMIN

- Maximum # SAQs used (ingress)

- Maximum # SAQs used (egress)

- Total # of active SAQS

## RECN Performance

- SAQ utilization – Traces, Comp. Factor 40, 64x64 BMIN

- Maximum # SAQs used (ingress)

- Maximum # SAQs used (egress)

- Total # of active SAQS

## RECN Performance

- Network throughput – Corner Case 2, 256x256 BMIN

## RECN Performance

- Network throughput – Corner Case 2, 512x512 BMIN

## Concluding remarks

- RECN reacts much faster than traditional congestion management techniques while being efficient and scalable
- However:
- RECN does not eliminate congestion
- RECN has not been adapted to wormhole switching
- RECN does not support adaptive routing yet
- Congestion management is not enough to provide guarantees when partitioning and virtualization are used, but helps keeping performance stable