EE 7725 Lecture Notes

Generated from file lslimr.dvi.

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.

MR-1                                                                                               *
 *         MR-1


                                        Midterm Exam Review


        General Information


             -  Open book, open notes.


             -  Tuesday, 29 October 1996, Time Change:  18:40.


             -  Fifty minutes, room TBD (come to this room first).


             -  Bring anything except a communication device.


             -  Two regular problems.


             -  One set of short-answer questions.


        Major Topics


             -  Overview of Parallel Processing


             -  Performance Model


             -  Major Network Types


             -  Network Measures


             -  Direct Networks


             -  Routing


             -  Equivalence



MR-1                      EE 7725 Lecture Transparency. Formatted 12:46, 25 October 1996 from lslim*
 *r.                  MR-1

MR-2                                                                                               *
 *         MR-2


                                 Overview of Parallel Processing


        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, : : :



MR-2                      EE 7725 Lecture Transparency. Formatted 12:46, 25 October 1996 from lslim*
 *r.                  MR-2

MR-3                                                                                               *
 *         MR-3


        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.



MR-3                      EE 7725 Lecture Transparency. Formatted 12:46, 25 October 1996 from lslim*
 *r.                  MR-3

MR-4                                                                                               *
 *         MR-4


        Bounds


                Link-length bound


                Moore Bound


                Derivation


        The k-ary n-Cubes


                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.


        Direct Network Routing


                Definitions of deadlock, livelock.


                Conditions for deadlock.


                E-cube routing.


                Two-level virtual channel flow control.


                Using "turn model" to show a network deadlock free.


                Deadlock free adaptive routing methods in KNCs.



MR-4                      EE 7725 Lecture Transparency. Formatted 12:46, 25 October 1996 from lslim*
 *r.                  MR-4

MR-5                                                                                               *
 *         MR-5


        Omega Networks


                Structure, routing, measures.


                Find path taken by a request.


                Types:  generalized, modified.


        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.



MR-5                      EE 7725 Lecture Transparency. Formatted 12:46, 25 October 1996 from lslim*
 *r.                  MR-5