Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 1 of 43 PageID #: 1794
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 1 of 43 PagelD #: 1794
`
`EXHIBIT A
`EXHIBIT A
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 2 of 43 PageID #: 1795
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 2 of 43 PagelD #: 1795
`
`
`
`Pu.) ——a4” PHOTOGRAPHIC MICROCOPY TARGCT
`
`10108 ANSI/ISO #2 EQUIVALENT
`
`LOic|Ee
`ws Ae 22
`- as
`elie
`les*gy
`eg ee
`
`PRECISION™ RESOLUTION TARGETS
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 3 of 43 PageID #: 1796
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 3 of 43 PagelD #: 1796
`aaa ol Canada ad
`acre
`Nabonal Libr
`Ges services biblographiques
`Solcorenic Gervices Branch
`Dwection des acquisdions et
`suacce
`KIAOM
`
`~ Whe ereree
`
`and
`
`385 Weangton Sireet
`KIA ONS
`
`NOTICE
`
`The quality of this microform is
`heavily dependent upon the
`quality of
`the original
`thesis
`submitted
`for
`microfilming.
`Every effort has been made to
`ensure the highest quality of
`reproduction possible.
`
`tae te ee etree
`
`AVIS
`
`La qualité de cette microforme
`dépend grandementde la qualité
`de
`la
`thése
`soumise
`au
`microfilmage. Nous avons tout
`fait pour assurer une qualité
`supérieure de reproduction.
`
`If pages are missing, contact the
`university which granted the
`degree.
`
`S'il manque des pages, veuillez
`communiquer avec |'université
`qui a conféré le grade.
`
`Some rages may haveindistinct
`print
`.specially if
`the original
`pages were typed with a poor
`typewlter
`ribbon
`or
`if
`the
`university sent us an inferior
`photocopy.
`
`de
`d'impression
`qualité
`La
`certaines pages peut
`laisser a
`désirer,
`surtout
`si
`les pages
`originales
`ont
`été
`dactylographiées 4 l'aide d'un
`ruban usé ou si I'université nous
`a fait parvenir une photocopie de
`qualité inférieure.
`
`Reproductionin full or in part of
`this microform is governed by
`the Canadian Copyright Act,
`R.S.C.
`1970,
`c. C-30,
`and
`subsequent amendments.
`
`La reproduction, méme partielle,
`de cette microforme est soumise
`4 la Loi canadienne sur le droit
`d'auteur, SAC 1970, c. C-30, et
`ses amendements subséquents.
`
`Canada
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 4 of 43 PageID #: 1797
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 4 of 43 PagelD #: 1797
`
`Routing and Broadcasting in
`‘Two-dimensional Linear Congruential Graphs of Degree Four
`
`Kuo-Jui Raymond Lin
`
`A Thesis
`
`in
`
`The Departmer*
`
`of
`
`Computer Science
`
`Presented in Partial Fulfillment of the Requirements
`for the Degree of Master of Computer Science at
`
`Concordia University
`
`Montreal, Quebec, Canada
`
`June 1994
`
`© Kuo-Jui Raymond Lin, 1994
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 5 of 43 PageID #: 1798
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 5 of 43 PagelD #: 1798
`
`Bei cota”
`Bolnoreniia Gevices Branch
`‘Ss
`and
`sores
`KIAQM
`
`nyt alae
`des servicesbiblographiques
`Direction 0es acquisaions et
`meow
`KIA OM
`
`tare Wee eens
`
`we SP Orne
`
`THE AUTHOR HAS GRANTED AN
`IRREVOCABLE NON-EXCLUSIVE
`LICENCE ALLOWING THE NATIONAL
`LIBRARY OF CANADA TO
`REPRODUCE, LOAN, DISTRIBUTE OR
`SELL COPIES OF HIS/HER THESIS BY
`ANY MEANSAND IN ANY FORM OR
`FORMAT, MAKING THIS THESIS
`AVAILABLE TO INTERESTED
`PERSONS.
`
`L'AUTEUR A ACCORDE UNE LICENCE
`IRREVOCABLE ET NON EXCLUSIVE
`PERMETTANT A LA BIBLIOTHEQUE
`NATIONALE DU CANADA DE
`REPRODUIRE, PRETER, DISTRIBUER
`OU VENDRE DES COPIES DE SA
`THESE DE QUELQUE MANIERE ET
`SOUS QUELQUE FORME QUE CESOIT
`POUR METTRE DES EXEMPLAIRES DE
`CETTE THESE A LA DISPOSITION DES
`PERSONNEINTERESSEES.
`
`THE AUTHOR RETAINS OWNERSHIP
`OF THE COPYRIGHT IN HIS/HER
`THESIS. NEITHER THE THESIS NOR
`SUBSTANTIAL EXTRACTS FROMIT
`MAY BE PRINTED OR OTHERWISE
`REPRODUCED WITHOUT HIS/HER
`PERMISSION.
`
`L'AUTEUR CONSERVE LA PROPRIETE
`DU DROIT D’AUTEUR QUI PROTEGE
`SA THESE. NI LA THESE NI DES
`EXTRAITS SUBSTANTIELS DE CELLE-
`CI NE DOIVENT ETRE IMPRIMES OU
`AUTREMENT REPRODUITS SANS SON
`AUTORISATION,
`
`ISBN 0-315-97642-x
`
`Canadii
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 6 of 43 PageID #: 1799
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 6 of 43 PagelD #: 1799
`
`some Clo~Tiki RAYMOND Lal
`
`Dissertahon Absiract internakonal is arranged by brood. general wbyect
`108.
`Pleose select the one subject which mos!
`nearly describes the content of your dusertahon Enter the corresponding hour
`code wn the spoces
`prow:
`
`( eaMsuter
`
`CUCe
`
`ee§
`
`aates?
`
`SEREEESES
`
`ie
`
`EStEER:
`
`
`£fEfeStecyESkEFEESSSSESEEE it
`
`SAS
`
`get
`
`$SEEEEE
`
`SEESSEEEE
`EgeSSE
`
`&e >
`
`3
`
`Secestesy
`
`i
`
`iH:
`ilPil
`
`ifamli
`
`seass
`
`osi0
`O31!
`
`2¢2s=
`
`Feb
`
`SE
`
`t
`
`Hey
`
`geeEih:@ESESSSESEREFISSTESESESESEFEEERELESES
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 7 of 43 PageID #: 1800
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 7 of 43 PagelD #: 1800
`
`CONCORDIA UNIVERSITY
`
`School of Graduate Studies
`
`This is to certify that the thesis prepared
`
`By:
`
`Entitled:
`
`Kuo-Jui Raymond Lin
`
`Routing and Broadcasting in
`Two-dimensional Linear Congruential Graphs of Degree Four
`
`and submitted in partial fulfillment of the requirements for the degree of
`
`Master of Computer Science
`
`Complies with the regulations of this University and meets the accepted standards
`with respect to originality and quality,
`Signed bythe final examining committee:
`
`
`
`eeeeyae Examiner
`
`Chair
`
`External Examiner
`
`> —
`
`Examiner
`
`Thesis Supervisor
`
` Approvedby——hg
`
`hair-oLdepastimentor/Graduate Program Director
`
`fuses 1g AAaeee
`
`Dean of Faculty
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 8 of 43 PageID #: 1801
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 8 of 43 PagelD #: 1801
`
`Abstract
`
`Routing and Broadcasting in
`Two-dimensional Linear Congruential Graphs of Degree Four
`Kuo-Jui Raymond Lin
`
`A two-dimensional linear congruential graph G({ fi, fo,-++, a}, (915 42)), or 2-D LC
`graph for short, of size s; x s) is a graph in which the set of vertices is the set of
`pairs of integers {(2,y) | 0 S 2 < 5,0 < y < 59}, and there is an edge from(z, y)
`to fi(z,y) mod(9), 43) for any (z,y) and anyfunction in the set {/i, fa,--+, fa) of
`two-dimensional linear functions. 2-D LC graphs were jntroduced in [1].
`In this thesis, we consider the problems of routing and broadcasting in 2-D LC
`graphs of degree 4 in which /, generates a Hamiltonian cycle, and fy generates a few
`disjoint cycles. First, some symmetric properties of 2-D LC graphs are discussed. We
`then discuss a greedy global routing algorithmwith a breadth first search scheme,
`which uses a large numberof path tables, and provide a moreefficient scheme having
`only one path tablefor all vertices of a graph. Two depthfirst distributed routing
`algorithins are proposed,
`In absence of faults, both algorithms route messages along
`the shortest path betweena pair of vertices. They are evaluated in various cases of
`faults. We also discuss an algorithm for finding a setof disjoint paths betweena pair
`of vertices. A broadcasting algorithm in LC graphs is proposed. We give functions
`for which the broadcasting can be done in time O(log, n), whichis asymptotically
`optimal, We then investigate the broadcasting problem for 2-D LC graphs and
`propose strategies that improve the broadcast time,
`
`iii
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 9 of 43 PageID #: 1802
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 9 of 43 PagelD #: 1802
`
`Acknowledgement
`
`First, | wish to express mysinceregratitudeto mythesis supervisor, De. Jaroslav
`Opatrny, for his excellent guidance and kindly support during the course of this
`thesis.
`I amalso grateful for his patience and enicouragenient,
`
`thank Mr. Ching-Chun Koung for his encouragement and friendship. His work
`on the properties of the network model has inspired ideas and his diligence has
`influenced me in more ways than he knows.
`
`I appreciate myparents for their constant support, and finally 1 thank my wife
`for her consideration and support.
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 10 of 43 PageID #: 1803
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 10 of 43 PagelD #: 1803
`
`Dedicated to my parents
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 11 of 43 PageID #: 1804
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 11 of 43 PagelD #: 1804
`
`Contents
`
`1
`
`Introduction
`1.1 Motivation and Problem Domain ....................
`BS UmeeOune. sso csccseveredevecacesesnanee,
`
`l
`1
`4
`
`6
`2 Review of Current Network Models
`A ee erie 6
`2.1.1
`Basic Notations of Graph Theory .. 2.2. ......0....
`7
`2.1.2 Network Topology, Routing and Broadcasting Algorithms...
`8
`22 The Hypercube Graph .. 0.2... we cece cee i
`2.2.1 Definitions and Properties 2. 2... ee ee eee lt
`2.2.2 Routing and Broadcasting Algorithms ............, 12
`2.3 The de Bruijn Graph... 2. eee eee Ee
`2.3.1 Definitions and Properties»... 2... 00 ee Ih
`2.5.2 Routing and Broadcasting Algorithms ............. is
`Me ne ee 20
`24.1 Definitions and Properties»... ......0.000.0-2-.. 20
`24.2 Routing and Broadcasting Algorithms ............. 23
`
`30
`3 Symmetries in Two-Dimensional Linear Congruential Graphs
`Bl Ss gas aa Sa eke thea aan ode Aw ak xa kon 30
`3.2 Review of Properties of Linear Congruential MADER 63% Be ww eave
`32
`3.3 Symmetric Properties of Two-Dimensional Linear Congrucntial Graphs
`Sis es Ce ee ie. Skee mtwkebeven ene vereneun MM
`3.3.1 Graphs of Simple Form... 6.6... ce eee ee 35
`4.3.2 Graphs of Complex Form .. 2... 060.0 eee eee 45
`
`vi
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 12 of 43 PageID #: 1805
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 12 of 43 PagelD #: 1805
`
`4 Routing Algorithms of Two-Dimensional Linear Congruential Graphs 53
`CL CROMRE sos e cde s ep ase be ends ORs we ees 53
`4.1.1 Global Routing in Graphs of Simple Form 2.2... 2.0... 55
`4.1.2 Global Routing in Graphs of Complex Form .......... 60
`4.1.3 Comparison of the Global Routing in Graphs of Simple Form
`SCE ta sa 46 2% 09 0059 be RID Ow 61
`4.2 Global Routing in Graphs of Simple Form with a Unique Path Table
`63
`4.2.1
`Construction of the One-to-one Mapping Path Table
`.. .
`.
`. 65
`4.2.2 Construction of the Mapping Table .. 2... 2.2.2.0. 70
`
`ee MERIOMEIOG 5.60 be wine 4 80.8 0 BEAD OOo Weare areas 73
`GNNO a ee 74
`
`4.3.1 Construction of Length Tables. 2... 2... 0.0.02.0..
`
`76
`
`Sid ‘COMVIW AIMEE«ccc eer eceneseeseive 78
`4.3.3
`Progressive Algorithm ........000cseenececves 80
`Be SEE arts na b kare wed wre PRETO 8-488 vee 82
`
`4.4
`
`Finding Disjoint Paths .........cccsesvevvevsevavces 4
`
`.ccrcvesvsecevereeuses 87
`SA:1 Conmoctivity ofaagraph
`4.4.2 Algorithm of Finding Disjoint Paths .............. 88
`Mae “Sh eee se ae wn eea eine wes enweas 96
`gs ier a rr 97
`4.5.1
`Introduction and Definition .. 2... ........0.0.5.
`97
`
`4.5.2 Broadcasting Algorithm ......+ 00000 ceveeeces 99
`Se)OREN) da din oie 4 6as a ba Bae Ele £608 RoE RES 120
`
`124
`5 Conclusion
`+ 12
`1) OME AOU 5 pushin oe alee-e dene MaDe sue ecek »
`Se ERORCHMMMMMEE naw i oxdwesarcesaaribeaean 126
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 13 of 43 PageID #: 1806
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 13 of 43 PagelD #: 1806
`
`List of Figures
`
`22
`2.1 Two ways of decomposing a 4-star graph»... 0.000005 ce,
`2.2
`n— 1 disjoint paths between two vertices of S.. 2... ke 26
`
`3.1 Two-dimensional Linear Congruential graph G({ Si, fa), (2', 52)) of
`PION. 6.05 ce siLaT A Sie wale’ ks Med dale anhico ‘7
`
`4.1 Data structure of global routing... 6. oe ee ee ee 56
`4.2 Paths with the same value of A(p)
`.....00.0000 0c cece.
`72
`OD:NE bo. ois Hk ce rea eew ee Bead SweeR came Le: 0
`44 Upper bound on lengths of disjoint paths ,...........0066. os
`4.5 Broadcasting Algorithm 2.0.0.0. 000 0000 cee ee ev ccee 100
`4.6 Broadcasting in a one-dimensional graph containing f;(z) = 241 .
`. 102
`4.7 Broadcasting in a one-dimensional graph ............05., il
`4.8 Broadcasting in a two-dimensional graph of simple form... 2... 1s
`4.9 Modified broadcasting algorithmfor Strategy3............., 119
`
`viii
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 14 of 43 PageID #: 1807
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 14 of 43 PagelD #: 1807
`
`List of Tables
`
`. 2... ...-0044., 62
`‘The shortest-path table for vertex (0,0) of G,
`4.1
`4.2. The shortest-path table for vertex (0,0) of Go... ee 63
`4.3 An example of the djo-table ......0.0. 00000 ee eae ee.
`74
`4.4 Comparison of two global roccting algorithms . 2... 0.0.00. 75
`15 Comparisonof two distributed routing algorithms ........ 0... 85
`1.6 Comparisonof two distributed routing algorithms (continue)... . 86
`4.7
`‘Test results of finding disjoint paths... ........0..-5.086 96
`1.8 The actual run-time of broadcasting. ........0..0..-50006 115
`1.9 The expected broadcast time... 6.00606 ee ee eee ees 115
`4.10 The test results of Strategy)... Ce ee eee 117
`4.11 The test results of Sirategy2.. 1... ccc cee ec cc cee ncee 118
`4:12 Evaluation of Sirategyd 2. cc ncncsvccccccceecuces 120
`4.13 Evaluation of empirical broadcast time... 2... 0... ee eee 122
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 15 of 43 PageID #: 1808
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 15 of 43 PagelD #: 1808
`
`Chapter 1
`
`Introduction
`
`1.1 Motivation and Problem Domain
`
`Hecause of the advance in VLSI technology, the continuing decline in the cost of
`microprocessors and the demand for reliable computing systems with high total
`computing power, manyresearch efforts have been madeto design massively parallel
`processors. One of these systems is the multicomputer system, A multicomputer
`systemconsists of a set of computers interconnected by a network in whieh a typical
`computer might consist of a main processor, a local memory and a communication
`processor to control the communications with other computers in the system. As
`the processing resources, control and data aredistributedin these systems, they are
`more reliable than the systems with a single processor,
`Many problems that cannot besolved efliciently by sequential computers can be
`divided into smaller tasks or subproblems that can be executed in parallel. Each of
`these tasks may be assigned to a processor. After a processor finishedits task, the
`result may be sent to other processors. Communication among processors in such a
`network is achieved by a message passing protocol.
`In the design of a massively parallel computers system, one of the important
`design decisions is the topology of the network interconnecting all computers in the
`system, Some basic considerations concerning the interconnection network are as
`follows, The numberof processors must be large enoughto meet the demand for high
`total computing power, The number of communication links at each computer must
`be small since the number of connection pins is limited. ‘To maintain a low Message
`latency, the distance (minimum numberof links) between any two computers must
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 16 of 43 PageID #: 1809
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 16 of 43 PagelD #: 1809
`
`be stall
`
`ln the design of computer networks, graphs are usually used to model the com-
`puter networks, in which the vertices correspond to the computers in the networks,
`and the edges correspond to the communication links.
`In graph theoretic terms, a
`graph corresponding lo a network having th. above desirable properties is a graph
`having large size (i.c., large number of vertices), small degree and small diameter.
`However, these three parameters are mutually related. For example, given a degree
`A and diameter D, the size S of a graph that can be constructed is bounded. It is
`so-called (A, D)-graph problem,
`Moore provided an upper bound on the size of a graph with given degree and
`diameter as follows.
`
`S(A, D) = 1444+ A(A = 1) 4-5-4 A(A=-—1)?"!
`
`Many research efforts have been made to construct graphs of size near the upper
`bound.
`It has been proved that the complete graph (D = 1, any A), rings (any D,
`A = 2), Petersen graph (D = 2, A = 3) as well as Hoffman and Singleton graph
`(D = 2, 4 = 7) attain the upper bound, However, for D > 2 and A > 2, the Moore
`bound is unattainable [2, 3).
`In addition to the above desirable properties of interconnection networks, some
`other issues on network performance are fault-tolerance, traffic congestion and ease
`of routing. A network with redundant paths between pairs of nodes can tolerate
`more faulty nodes o¢ communicationlinks. Therefore, the number of disjoint paths
`between any two vertices should be as large as possible. However, the maximum
`number of disjoint paths is bounded by the degree of a graph. A network that has
`its links uniformly distributed can be expected to minimize the congestion problem.
`The property of every vertex having the same number of incident edges (i.e., regular
`graph) is thus desirable. A symmetric topology of a network allows the use of
`identical processors at every node since every node plays an identical role in the
`network. The same routing algorithm can thus be applied to each node. It enables
`the design of low cost routing hardware.
`Hased on the above considerations, some graphs have been proposed as good
`candidates for interconnection networks such as hypercubes [4, 5, 6}, de Bruijn
`
`2
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 17 of 43 PageID #: 1810
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 17 of 43 PagelD #: 1810
`
`graphs (7, 8, 9] and star graphs (10, 11, 12]. De Bruijn graphs and their variations
`are well known large graphs of a given degree and diameter, Recently, a new class of
`graphs, called (multidimensional) linear congruential graphs, has been proposed (13,
`\]. A two-dimensional linear congruential graph G({fi, fa.s+>s Se), (a1, 42)) of size
`3) X 42 and degree 2k is a graph in which the set of vertices is the set of pairs
`of integers {(z,y) | 0 < x < 5:,0 < y < 54} and thereis an edge from (z,y) to
`Jilz,y) mod (5), 32) for any (x,y) and any functionin the set (Sis Sayre Sa) of two
`dimensional linear functions, It provides a uniform method to construct very large
`graphs for any fixed degree and size.
`It has been shown that with a proper choice of functions, a two-dimensional
`linear congruential graph is larger than the de Bruijn graph of the same degree and
`diameter, and it is regular and maximally connected (i.e., the number of disjoint
`paths between any pair of vertices of a graph is equal to the degree of the graph).
`Moreover, we have proved that they have some symmetric properties.
`In other
`words, two-dimensional linear congruential graphs have the desirable properties of
`interconnection networks. Motivated by these properties, the aim of our research is
`to investigate the routing and broadcasting in two-dimensional linear congrucntial
`graphs, in particular, of degree four,
`Anefficient message routing scheme is one of the most important components
`of a multicomputer system. To decrease the message latency, sending messages
`along the shortest path between given source and destination nodes is expected,
`In general, there are two types of routing schemes, global routing and distributed
`routing, for sending a message from a source node to a destination node.
`In a global routing scheme, the decision of a route for sending a message is made
`at the source node. There are two ways to decide a route. One way is to construct
`a table at each node, The table contains the shortest paths from the node to each
`other nodes, Whenever a node wants to send a message, the node simply checks the
`table to decide a route. This way is usually used when the calculation of a route is
`time-consuming. Another wayis to re-calculate a route at a source node whenever
`a message will be sent by the source node.
`In distributed routing scheme, a route for sending a message is not completely
`decided by the source node, but by each intermediate node traversed by the message.
`
`J
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 18 of 43 PageID #: 1811
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 18 of 43 PagelD #: 1811
`
`Each intermediate node chooses a link that probably leads to a shortest path to the
`destination of the message to forward the message.
`
`Since a multicomputer system may consist of a large number of nodes and com-
`municationlinks, it is possible that some nodes or links in the systemfail. Therefore,
`a fault-tolerant routing scheme is required especially when a multicomputer system
`is used in a mission-critical application. It should be able to send messages as long
`as the source and destination nodes are connected. In global routing scheme, cach
`node must have the knowledge of all faulty components(i.e., faulty nodes and links)
`since @ route is completely decided at a source node.
`It is costly to maintain the
`knowledge. On the contrary, in distributed routing scheme, each node may only
`have to know the conditions of its incident links and adjacent nodes since the sout-
`ing decisions are made at each intermediate node. However, due to the lack of global
`knowledgeof faults, a path determined by this scheme may not be the shortest,
`As we mentioned, the existence of multiple disjoint paths betweenpairs of nodes
`implies that a network can tolerate more faults.
`In addition, message congestion
`can be minimiced since messages between the same pair of nodes can be sent along
`disjoint paths.
`Broadcasting generalizes the routing process. It is a process of sending a message
`froma node to all other nodes in the network in which any node that already received
`the message can send a message to at most one of its neighbors in one time unit.
`broadcasting is an important part of many parallel algorithms, Loading the same
`programcode from a front end to all the processors in a multicomputersystemis a
`typical example of broadcasting [14].
`
`well-known graphs; hypercubes, de Bruijn graphs and star graphs.
`
`1.2 Thesis Outline
`
`In the next chapter, two major categories of parallel processing: multicomputer and
`multiprocessor are introduced, Somebasic notations of graph theory are reviewed.
`The performance and cost issues in the design of a network topology are discussed.
`Formal definitions of global routing, distributed routing, disjoint paths and broad-
`casting are given, We then review the routing and broadcasting algorithms for some
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 19 of 43 PageID #: 1812
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 19 of 43 PagelD #: 1812
`
`In Chapter J, we review some definitions and properties of linear congrucntial
`graphs. Some symmetric properties of one- and two-dimensional linear congruential
`graphs of degree four are proved.
`In Chapter 4, the problems of global routing, distributed routing, finding disjuint
`paths and broadcasting in two-dimensionallinear congrucntial graphs of degree four
`are discussed,
`A global routing algorithm using a breadth first search approach is proposed,
`The aumber of path tables used by this algorithm for a graph is proportional to the
`size of the graph. Therefore, a moreefficient global routing algorithm is discussed,
`It only uses a unique path table anda very small size-independent mapping table for
`all vertices of a graph. Furthermore, the maximum length of any path determined
`by this algorithmis very close to the diameter of the graph,
`Twodistributed routing algorithms are investigated. They both use a depth first
`search approach and route messages along the shortest path in absence of faults in
`the network. Empirical results for these two algorithms applying in various faulty
`conditions are given.
`Analgorithmthat canfind the maximumnumberof disjoint paths for any pair
`of vertices is proposed, The lengths of the disjoint paths are bounded.
`We propose a broadcasting algorithm that provides an upper bound O(logyn)
`on broadcast time of certain one-dimensional linear congruential graphs, where n
`denotes the size of a graph. However,
`it does not generalize in a simple way to
`two-dimensional linear congruential graphs. ‘The empirical broadcast times of two-
`dimensional linear congruential graphs are evaluated. The broadcasting in two
`dimensional linear congruential graphs can be done in time similar to the time re
`quired for s'e Bruijn graphs of the same degree and comparable size, ‘Three strategies
`to improve broadcast time are discussed.
`Chapter 5 presents conclusions.
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 20 of 43 PageID #: 1813
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 20 of 43 PagelD #: 1813
`
`Chapter 2
`
`Review of Current Network
`Models
`
`2.1 Overview
`
`The multiprocessor and multicomputer are (wo major categories of parallel proces-
`sors. A multiprocessor systemconsists of a set of n identical processors and a global
`memory. The memory can be considered as if it were split into n "banks", and
`shared among the n processors, Communication among the processors is via shared
`memory. The primary advantage of multiprocessor systems is that the data access
`is transparent to the user,
`i.c., the user may consider the data as being kept in
`« large memory, which is accessible to any processor. The architecture makes the
`programming of the machine easy. However, it may lead to memory contention and
`thus degrade the performance of system.
`A multicomputer system consists of a set of processors, each of which has its
`ownlocal memory (hence each processor can be considered as a computer). There
`is no shared memory and no global synchronization. Communication among the
`processors is via message passing, and computation is data driven. The primary
`advantage of such architecture is the simplicity of its design. The nodes are identical
`or of a few different kinds. Thus the system can be constructed at relatively low
`cost,
`
`Whether a parallel processors system is implemented by a shared memory multi-
`processor or @ message passing multicomputer, an efficient interconnection network
`to interconnect the communicating elements is important for the performance of the
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 21 of 43 PageID #: 1814
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 21 of 43 PagelD #: 1814
`
`system.
`Before we discuss the performanceofinterconnection networks according to the
`properties of their related graphs, some basic notations of graphs will be reviewed
`below [15, 16, 17].
`
`2.1.1 Basic Notations of Graph Theory
`
`A graph G(V, E) consists of two sets: a finite set V of elements called vertices and a
`finite set E of elements called edges. Each edge is identified with a pair of vertices,
`If the edges of a graph G are identified with unordered pairs of vertices, then G is
`called an undirected graph.
`The vertices u and v associated with an edge ¢ are called the end vertices of c.
`The edge ¢ is then denoted as ¢ = (u,v). All edges having the same pair of end
`vertices are called parallel edges, Ife = (v,v), then the edge ¢ is called a self-loop
`at vertex v. A graphis called a simple graph if it has no paralle] edges or self-loops.
`We will focus our attention on undirected simple graphs,
`If there is an edge ¢ = (u,v), then we say that edge e is incident with vertex u
`(or v), and vertices u and v are adjacent. If two edges €, and ez have a commonend
`vertex, edges ¢, and €9 are said to be adjacent,
`The size of a graph G(V,E) is the number of vertices in V and is equal to | V].
`The degree of a vertex is the number of edges incident with the vertex. The
`degree of a graph G is the maximum degree among all vertices of G and is denoted
`by 4. A Graph in whichall vertices have the same degree is called a regular graph.
`A path of length n from the vertex u to the vertex uv is a sequence €,¢3-*- eq
`of edges together with a sequence vj 02+++ Ung: of vertices where ¢, = (1, v41) for
`Si sn, and uy = u, vag: = v. We will usually denote the path as vu; —* vy -+
`
`e° =O Unel-
`The distance between two vertices of a graphis the length of the shortest path
`between them, The diameter of a graph G is the maximumdistance amongall pairs
`of vertices of the graph and is denoted by D(G).
`A path with a sequence v;¥2-++vn41 of vertices is closed if vy, = vpy).
`vertices uj, Ug, ***, Up are all distinct, the closed path is called a cycle.
`A path with a sequence v, 0, ---U, of vertices is called a Hamiltonian path for a
`
`If the
`
`:
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 22 of 43 PageID #: 1815
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 22 of 43 PagelD #: 1815
`
`graph G(V,E) if uy, vy, «++, Up, are all distinct and {¥j,U2,°°*, Ua) = V. A cycle
`Ui Vye+ Uv; is called a Hamiltonian cycle if vjvg---v, is a Hamiltonian path. A
`graph that has a Hamiltonian cycle is called a Hamiltonian graph.
`A graph G'(V’, E’) is a subgraph of a graph G(V, £) if V' and £° are subsets of
`V and E, respectively, such that an edge (u,v) is in £’ only if u and v are in V’.
`A graph is called connected if every pair of distinct vertices is joined by a path.
`The removal of a vertex v from a graph G induces a subgraph of G that containsall
`vertices except v and the edges not incident with v. The connectivity of a graph is
`the minimum number of vertices that need to be removed to disconnect the graph.
`A family of graphs {G,,G),°+*,G,,-++) is said to be recursive if G; can be
`obtained from a number of copies of Gj, by some simple operations, and G)-, is a
`subgraph of G;.
`An isomorphismof a graph G\(VYj, E;) onto a graph G2(V2, £)) is a one-to-one
`correspondence a : V, — V, such that (u,v) is in £, if and only if (a(u),a(v)})
`is in £y. Two graphs G, and G, are isomorphic, written G; ~ Go, if there is an
`isomorphisin a of one onto the other, An isomorphismof a graph ontoitself is called
`an aulomorphismof the graph. A graph is vertez-transitive if and only if for every
`pair of vertices uv; and v, there is an automorphismof the graph that maps v; into
`vy. A graph is edge-transitive if and only if for every pair of edges ¢, and e3, there
`is an automorphismof the graph that maps e, into e.
`
`2.1.2 Network Topology, Routing and Broadcasting Algo-
`rithms
`
`The interconnection topology and related routing algorithm are two majorissues in
`the design of an interconnection network. In choosing a topology, two factors: the
`cost and performance should be carefully considered [18]. Since we use graphs to
`model interconnection networks, we wil! analyze the performance andcostissues in
`graph theoretic terms.
`In order to achieve high performance within an interconnection network, the
`following properties of the corresponding graph are desirable.
`
`# Small diameter: messages in a network may pass through a numberofinter-
`mediate nodes before reaching their destinations. At each intermediate node,
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 23 of 43 PageID #: 1816
`Case 1:16-cv-00453-RGA Document 22-1 Filed 10/04/16 Page 23 of 43 PagelD #: 1816
`
`both the message processing overhead and queuing delayresult in the com-
`munication latency experienced by a message. Small diameter of the graph
`means that few number of intermediate nodes are visited by every Nicssage,
`Thus the communicationtime is kept relatively short.
`
`Regular graph: If some of nodes in the network have less links than the others,
`it is likely for the network to have bottlenecks at these nodes, A regular graph
`has all of its edges uniformly distributed, therefore reducing the probability of
`the occurrence of bottlenecks.
`
`If there are many possible paths between each pair of
`Large connectivity:
`nodes in a network, in the presence of faults, the communication between non-
`faulty nodes may continue to work in a higher probability. High degree of
`connectivity prevents the non-faulty nodes from disconnected. (A graph with
`connectivity m can tolerate at least mn — 1 faulty nodes.)
`
`9
`
`Obviously, some of the above properties are conflicting. For example. a graph
`with small degree cannot have large connectivity, Thus any decision made in choos-
`ing & topology will experience a tradeoff between cost and performance,
`In addition to choosing a topology for a network, we must also select an algo-
`rithm for transmitting messages through the network.
`‘This algorithm is called a
`routing algorithm. A routing algorithm is a set of rules that specifies, for each mes-
`sage, through which path to route the message and the data required to make such
`decision. We will focus our study on four algorithms: global routing, distributed
`routing, finding disjoint paths and broadcasting.
`
`Whenconsidering the cost of a network, two important properties of the corre-
`sponding graph should belisted:
`
`