MIT-REPORT

Synchronization and Pipeline Design for a Multithreaded Massively Parallel Computer

Shuichi Sakai

Computation Structure Group MIT-LCS

Acknowledgment

Dr. Sakai would like to thank

• Prof. Arvind, Prof. Papadopoulos, and Dr. G. A. Boughton for supporting his research (also his life),

• the members of CSG for the fruitful discussions (also for buying his items and carrying his boxes)

• Prof. Dennis and Dr. Nikhil for his helpful comments

• Ms. Maderer for her support.

Introduction

This presents the optimization of a synchronization and a pipeline in a multithreaded massively parallel computer.

Basic Strategies

(please do not be too serious....)

• study the past and the present

• use, improve or forget

• reconsider the proposal Remark: Here, we concentrate on data-driven sync. and a processor pipeline based on a dynamic model.

Proposed Data-Driven Synchronizations

• Hash in Manchester DFM and SIGMA-1 • ETS in the Monsoon

• Direct Matching in the EM-4

• Direct Match in Sandia Dataflow

• *T Synchronization

• Advanced Direct Matching in the EM-5

Matching by Pseudo Associative

Mechanisms = Hashing

Advantages

• high spatial efficiency

• flexibility Drawbacks

• complex

• pipeline bubbles caused by a hash-miss • difficult to understand what is happening (ETS in Monsoon)

7

Advantages

• no associative mechanisms

• no hash miss

• EXPLICIT = easy to understand what is/ should be happening

• matching word is reusable even in the same

function instance

Drawbacks

• instruction fetch is always necessary, even if match fails

• instruction fetch and matching must be serialized (Direct Matching)

9

Advantages

• no associative mechanisms

• no hash miss

• instruction fetch is not necessary for match

• ins. fetch can be performed in parallel with match.

• easy to understand what is happening Drawbacks

• TSN fetch overhead

• reuse of a frame word is difficult

• TSN write overhead at the function invocation time (small overhead)

*T Synchronization

= FORK and JOIN instructions • flexible for many types of synchronizations • longer turnaround

• using instruction execution cycles: overhead (originally it is a separate part of the processor)

(Advanced Direct Matching)

12

Advantages

• no associative mechanisms

• no hash miss

• instruction fetch and matching are completely independent and performed in parallel

• easy to understand what is/should be happening

• no TSN fetch and no TSN write Drawbacks

• hardware cost, especially bandwidth

Requirements for Synchronization in

Multithreading

(before showing the optimization... )

1. multi-way join

2. may not need as frequent sync. as pure dataflow

3. sync. must be fast enough to follow the localized exec., e.g. to follow the cache/ register cycle (Optimized Synchronization)

15

Opt. Sync. = modified advanced direct matching

• short pitch pipelining for cache/register architecture

• flag-cache/data-cache separation

• supporting five types of sync.

– monadic: no sync.

– dyadic: same as advanced direct matching

– multiway: counter join without using instructions

– signal sync.: multiway without data read/ write

– counter overflow: join tree

= SIMPLE, FAST and FLEXIBLE sync.

Optimizing a Pipeline

Proposed Pipelines

• Circular Pipe. in Manchester DFM, SIGMA-1

• Non-blocking Circular Pipeline in Monsoon • Layered Pipeline in EM-4 and EM-5

• *T Pipeline (not published)

(Monsoon Pipeline)

18

Advantages of a Circular Pipeline

• exploiting maximally the parallelism within a single pipeline

• natural and efficient combination of computation and communication

• excellent throughput even without complex interlocking and branch predictions Drawbacks of a Circular Pipeline

• no advanced control

• lots of bubbles for less parallel execution • inefficient resource management

Pipeline Fusion in a Multithreaded Computer

Integration of a Circular Pipeline and a von Neumann (RISC) Pipeline = keep the advantages and remove the drawbacks e.g. EM-4, *T, EM-5 (EM-4 pipeline)

21

Pipeline Optimization

Requirements for a Pipeline in a Multithreaded Computer

• high throughput for both multithreaded execution and single-threaded execution, i.e. 1 (or s) result(s) per one RISC clock

• short turnaround

– single-thread: as fast as or faster than sequential RISC

– multi-thread: 4 to 5 clocks between message input and output (Optimzed Pipeline)

23

Features of the Optimized Pipeline

• short-pitch: one cache cycle, achieved by multiport caches

• intra-PE parallelism

– instruction fetch-decode and synchronization

– flag handling and data handling

– parallelism among operational units – message generation and execution

• Packet Turn around – 4 clocks for monadic/dyadic

– 4 + (s-2) clocks for s-adic

Architectural Tuning

1. Priority Control for short prior thread, for supervisor thread, etc.

• independent pipeline: *T

• multiple register set

• priority queue

2. Load/Store Overhead Elimination bypassing the write/read of multiway-join

3. More Flexible Thread Interleaving

• multithreaded floating pipeline

• multithreaded superscaler execution

Cost-Effectiveness

Proposed methods are cost-effective since: • amount of the logic is not much

• control is not complex, no interlocking between threads

• bandwidth – caches : OK since they are inside chip – network bandwidth: worth spending (one

additional field for the header)

Related Issues

• I-structure/M-structure Synchronization • Global Synchronization

• Cache Structure Optimization

• Scheduling Techniques

• Virtual Memory will be combined with the proposed mechanisms

Conclusion

This presents the optimization of a data-driven synchronization and a pipeline.

Future Problems

• quantitative evaluations by analyses and simulations

• consideration of the ”related issues”

• feasibility study by implementation and evaluations by the real machines with practical application programs Future Plan in Japan = NIPT/RWC

Project

• major fields: Optical, Neural, Theory, MPP

• to establish a truly effective programming model

• 16K to 64K PE system in 1996 (hopefully, EM-6) = 3 to 10 TFLOPS computer

• 1 M PE system in 2001 = fusion of soft-logic and MPP

JAPAN is waiting for you to attend it!!

ETL is also waiting for you.

• invited researcher: visit ETL and give a talk e.g. Prof. Dennnis, Prof. Arvind, Dr. Iannucci

• post-doctor

• permanent position (It’s new!!)

• MIT Japan Program