This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
01-1 *
* 01-1
EE 7725_Interconnection Networks
Interconnection Network: hardware used to connect the processors
in a parallel computer.
Course Organization and Policies
Grading and Assignments
- 30%, Midterm Exam
- 30%, Final Exam (Cumulative)
- 30%, Term Paper
- 10%, Homework Assignments (Approximately 6)
Term Paper
Answer the question given in the project handout.
Term project will help develop skills needed for Master's and Ph.D.
work.
- Reading and understanding journal papers.
- Discover new facts using published information and your own
analysis.
Text
No text required.
Papers and handouts will be made available.
01-1 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-1
01-2 *
* 01-2
Office Hours
Monday and Thursday, 14:00-16:30, 349 EE Building.
Prerequisites
Knowledge of computer architecture:
- Difference between bus and multiplexor.
- How memory is accessed.
- How cache and main memory are organized.
Basics of discrete mathematics:
- Set operations.
- How to specify members of a set.
Inductive proof.
Probability theory.
01-2 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-2
01-3 *
* 01-3
Parallel Computer
Motivation: Serial computers not fast enough.
A serial computer uses a single CPU.
Idea:
- Use more than one CPU.
- Divide problem into parts.
- Run each part on a CPU.
Parts of Parallel Computer
- Processing Elements (PEs)
Name for CPU in a parallel computers.
- Parallel Program
Program which runs on the PEs.
Parallel program divided into tasks.
Each task runs on one PE.
A PE can run any number of tasks.
SIMD Parallel Computer: PEs simultaneously execute the same
instruction. (Nearly obsolete.)
MIMD Parallel Computer: Each PE executes instructions on
its own.
- Interconnection Network
Used to connect the processors.
01-3 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-3
01-4 *
* 01-4
Hard Part of Parallel Processing
Parallel Algorithms
Communication
01-4 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-4
01-5 *
* 01-5
Course Topics
Importance of Networks in Parallel Processing
Performance Measures
System Performance Model
Types of Networks
Direct Networks
Measures
k-ary n-cube family.
de-Bruijn family.
Other networks.
Omega Networks
Performance Evaluation
Congestion Reduction /Fault Tolerance
Network Equivalence and Transformation
Omega Network Admissible Permutations
Clos and Benes Permutation Networks
Generalized Connectors
Sorting Networks
01-5 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-5
01-6 *
* 01-6
Performance Model
Goal: Show how parallel program and network interact.
Modeled System:
- N PEs.
- P tasks.
- An arbitrary (unspecified) network.
Each task:
1: Computes for tm units of time.
2: Sends a message to some other PE and waits for a response.
3: When the response arrives, task resumes computing.
Each PE:
- Has P =N tasks.
- Can run at most one task at a time.
The Network:
- Sends a message and return response in tnw units of time.
Quantity tnw called network latency.
This describes the quality of the network.
The Questions:
- How efficient is this system?
01-6 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-6
01-7 *
* 01-7
Measures of Performance
Let T (N ) be the amount of time to solve a problem on N processors.
Then, T (1) is the time on a serial computer.
Under reasonable conditions, T (N ) T (1)=N .
T (1)
The Speedup of a system using N PEs, S(N ), is the ratio _________.
T (N )
- A system exhibits linear speedup if S(N ) = N .
- A system exhibits superlinear speedup if S(N ) > N .
T (1)
The utilization of a system using N PEs, U (N ); is is ____________.
N T (N )
Utilization and speedup measure the same quantity in different ways.
01-7 EE 7725 Lecture Transparency. Formatted 11:00, 23 August 1996 from lsli01*
*. 01-7
| David M. Koppelman - koppel@ee.lsu.edu | Modified 26 Aug 1996 18:29 (23:29 UTC) |