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.
FR-1 Final Exam Review *
* FR-1
General Information
Tuesday, 9 December 1997, 10:00-12:00 CST.
Open book, open notes.
Two hours, this room.
Bring anything except a communication device.
Three regular problems.
One set of short-answer questions.
FR-1 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-1
FR-2 *
* FR-2
Major Topics
- Overview of Parallel Processing
- Performance Model
- Major Network Types
- Network Measures
- Direct Networks
- Flow Control
- Deadlock-free Routing
- Buffering
- Permutation Families
- Mathematical Representation
- Equivalence
- Delta and Bidelta Networks
- Circuit Switching Definitions
- Clos Networks
- Benes Networks
- Generalized Connectors
- Sorters, Balancers, and Counters
FR-2 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-2
FR-3 Overview of Parallel Processing *
* FR-3
Identify, know role of:
tasks, processors, network.
Performance Model
Know how equation parts relate to modeled system.
Know sequence of events as modeled program runs:
computation, message sending.
Major Network Types
Know distinguishing features of each.
- Bus: Shared Medium
- Direct: nodes connected by links.
- Crossbar: crosspoint for each input/output pair.
- MIN: Cells organized into stages, : : :
FR-3 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-3
FR-4 *
* FR-4
Network Measures
Structure:
Diameter, average distance, bisection width, degree.
Performance:
Latency, throughput.
Message Structure and Flow Control
Relationship between:
Message and packet.
Inputs, outputs, requests, and connection assignments.
Direct Networks
Graph Specification
Convert between
set G = (V; E) description, drawing, verbal description, etc.
Node Structure
Relationship between node, crossbar, processor, and links.
FR-4 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-4
FR-5 *
* FR-5
Moore Bound
Derivation
The k-ary n-Cubes, n-Dimensional Meshes
Description, measures
Routing
Important features: simple routing, many algorithms, etc.
The de Bruijn and Shu- e-Exchange Networks
Description, measures.
Routing.
Important features: small diameter, etc.
Omega Networks
Structure, routing, measures.
Find path taken by a request.
Types: generalized, modified.
FR-5 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-5
FR-6 *
* FR-6
Buffering and Flow Control
Queue placement and connection to crossbar.
Deadlock Free Routing
Virtual-channel flow control.
FR-6 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-6
FR-7 *
* FR-7
Permutation Families
Major Families
Shift
Bitonic (Spreading, Packing)
Admissibility Proofs
Admissibility function.
Mathematical Representation
Convert between: LGM, CGM, sets of permutations representations.
Equivalence
Know definitions of:
Descriptive, terminal, topological, and functional equivalence.
Be able to prove or disprove for a pair of networks.
Equivalence results for networks presented in class.
Delta and Bidelta Networks
Definitions
Path descriptors and dual-path descriptors.
Relationships
Banyan and Delta
Delta and Bidelta
Topological equivalence of any two bidelta networks.
FR-7 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-7
FR-8 *
* FR-8
Circuit Switching Definitions
Rearrangeable
Non-blocking, strictly non-blocking, wide-sense non-blocking.
d-limited generalized connection assignments.
Clos Networks
Non-Blocking
Definition, proof that it's non-blocking.
Rearrangeable
Definition.
Proof that it's rearrangeable.
Hall's theorem. (Statement, but not proof of Hall's theo-
rem.)
Proof of Clos network rearrangeability.
Routing. (The looping algorithm.)
Application of algorithm.
FR-8 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-8
FR-9 *
* FR-9
Benes Network
Benes Network Basics
Definition.
Recursive looping algorithm application and run time.
Benes/Clos Network Correspondence
Mapping between cells in a Benes and Clos network.
Use for routing.
Implication for Clos network input- and output-stage cells.
Generalized Connectors
Pack/Copy/Permute Type
Clos Type
Fanout/Concentrate Type
FR-9 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lslif*
*r. FR-9
FR-10 *
* FR-10
Sorters, Balancers, and Counters
Sorters
Definitions
Compare/exchange (CE) element.
Comparison network.
Sorting network.
Zero/One Theorem
Proof, application.
Balancers and Counters
Balancing element.
Definition of balancing and counting network.
Construction.
Applications.
FR-10 EE 7725 Lecture Transparency. Formatted 10:57, 5 December 1997 from lsli*
*fr. FR-10
| David M. Koppelman - koppel@ee.lsu.edu | Modified 5 Dec 1997 13:09 (19:09 UTC) |