`

`A
`w.
`
`IEEE COMPUTER S OCIETY ~
`~®
`
`The Computer Society is an association of people with i;irofessional interest in the fielti'of eomputers. All members of the IEEE are eligible for membership in the Society
`upon payment of the annual Society membership foe of$t5.00. Members of certain professional societies and other computer professionals are eligible to be members
`of the Computer Society. For information on joining write to the IEEE Computer Society, 1730 Massachusetts Avenue N.W., Washington, DC 20036-1903.
`
`IEEE TRANSACTIONS ON COMPUTERS
`MING T. (MIKE) LIU, Editor-in-Chief
`Dep. Comput. & Inform. Sci.
`The Ohio State Univ.
`2036 Neil Ave. Mall
`Columbus, OH 43210-1277
`
`BRYAND. ACKLAND
`AT&T Bell Labs .. 4Es508
`Holmdel , NJ 07733
`
`P. BRUCE BERRA
`Dep. Elec. & Comput. Sci.
`Syracuse Univ .
`111 Link Hall
`Syracuse, NY 13210
`
`JOHN A. DARRINGER
`IBM Corp .
`Rt. 100, P.O . Box 100, B-4
`Somers, NY 10589
`
`MILOS D , ERCEGOVAC
`Dep. Comput. S.ci.
`Univ. California
`Los Angeles, CA 90024
`
`GREG N. FREDERICKSON
`De.pt. of Comput. Sci .
`Purdue Univ ..
`West Lafayette. IN 47907
`
`VIJA y S. IYENGAR
`IBM T . J. Watson
`Res. Center
`P.O. Box 218
`Yorktown Heights,
`NY 10598
`
`LARRY ' .. KINNEY
`Dept. t1ec . Eng.
`Univ. Minneapolis
`Minneapolis. MN 55414
`
`WALTER H. KOHLER
`Digital Equipment Corp.
`I 5 I Taylor St.
`MROl-l /A65
`Littleton, MA 01460
`
`Editorial Board
`EDWARD D. LAZOWSKA
`Dept. Comp . Sci.
`Univ. of Washington
`Seattle. WA 98195
`
`Wu-HoN LEUNG
`AT&T Bell Labs.
`Naperville, IL 60566
`
`Y.TZHAK (HAIM) LEVENDEL
`AT&T Bell Labs, IX-G304
`Naperville, IL 60566
`
`DAVID C. L. LIU
`Dep. Comput. Sci.
`Univ . Illinois
`1304 West Springfield Ave .
`Urbana, IL 61801-2987
`
`JANE W. S. LIU
`Dep. Comput. Sci.
`Univ. Illinois
`Urbana Champaign , IL
`
`JOHN A. STANKOVIC
`Dep. Comput. & Inform .. Sci.
`Univ. Massachusetts
`Amherst, MA 01003
`
`G. M. MASSON
`Dep. Comput. Sci.
`The Johns Hopkins University
`Baltimore, MD 21218
`
`H. C. TORNG
`Sehl. Elec. Eng.
`Cornell Univ.
`Ithaca, NY 14853
`
`ROBERT J. T . MORRIS
`AT&T Bell Labs H0-3M331
`Crawfords Corner Rd .
`Holmdel, NJ 07733
`
`MASAHIRO TSUCHIYA
`Sypex International
`P.O. Box 1199
`Manhattan Beach, CA 90266
`
`KRISHAN KUMAR SABNANI
`AT&T Bell Laboratories
`600 Mountain Ave.
`Murray Hill , NJ 07974
`
`JEFFREY S. VITTER
`Dep. Comput. Sci .
`Brown Univ.
`Providence, RI
`
`THE COMPUTER SOCIETY
`PUBLICATIONS BOARD
`Vice President for Publications Activities: SALLIE V. SHEPPARD
`Vice Chairman:. JAMES J. FARRELL, III
`Secretary: JAMES CROSS
`Publications Finance Chairman: SALLIE V. SHEPPARD
`Publications Plannin1; Chairman : RICHARD BURKE
`Editors-in-Chief
`Advisory Committees
`Computer!Mar;azine Advisory:
`BRUCE D . SHRIVER
`SusHIL JAJODIA
`Tran<5a ctions Advisory:
`JoHN STAUDHAMMER
`P. BRUCE BERRA
`JOE HOOTMAN
`SUMIT DASGUPTA
`TED G. LEWIS
`DAVID PESSEL
`MrNG T. LIU
`VICTOR R. BASILI
`STEVEN L. TAN IMOTO
`C. V. RAMAMOORTHY
`
`,· ...
`
`'~'iEEE C.S. fob Liaison :
`;,,
`.
`
`DAVID CHOY
`
`Computer:
`IEEE CG&A:
`IEEE Micro:
`IEEE D&T:
`IEEE Software:
`IEEE Expert:
`IEEE TC:
`IEEE TSE:
`IEEE TPAMI:
`IEEE TKDE:
`
`Members-at-Large
`J. T. CAIN
`GLEN LANGDON
`HAROLD STONE
`
`Reps. to IEEE Publications Board: JAMES H. AYLOR, ANIL K. JAIN
`Rep . to IEEE TAB Periodicals Committee: JAMES H. AYLOR
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS' ENGINEERS, INC.
`1989 Officers
`
`EMERSON W. PUGH, President
`CARLETON A. BAYLESS, President Elect
`GEORGE F . ABBOTT, Executive Vice President
`HUGO RDCHARDT, SecretaJ)'
`WALLACE S. READ, Treasurer
`
`HARRY W. MERGLER, Vice President, Educational Activities
`EDWARD C. BERTNOLLI , Vice President, Professional Activities
`TIMOTHY N. TRICK, Vice President, Publication Activities
`MICHAEL J. WHITELAW, Vice President, Regional Activities
`H. TROY NAGLE, JR. , Vice President, Technical Activities
`
`THOMAS W. BARTLETT, Controller
`DONALD CHRISTIANSEN, Editor, IEEE Spectrum
`IRVING ENGELSON, Staff Director, Technical Activities
`LEO FANNING, Staff Director, Professional Activities
`ANDREW SALEM, Staff Director. Standards
`
`Director, Division V-Computer
`RoY L. Russo. Director, Division Vl/l-Computer
`Headquarters Staff
`ERIC HERZ, Executil'e Director and General Manager
`DAVID L. STAIGER, Staff Director, Publishing Services
`RUDOLF A. STAMPFL, StaffDirector, Educational Services
`CHARLES F. STEWART, JR. , Staff Director, Administration
`DONALD L. SUPPERS, Staff Director, Field Services
`THOMAS C. WHITE, Staff Director. Public Information
`
`Publications Department
`Publication Managers: ANN H. BuRGMEYER, GAILS . FERENC, CAROLYNE TAMNEY WALSH
`Associate Editor: DONNA INCORVAIA
`IEEE TRANSACTIONS ON COMPUTERS is published monthly by The Institute of Electrical and Electr'onics Engineers, Inc. Responsibility for the contents rests upon the
`authors and not upon the IEEE, the Society/Council , or its members. IEEE Headquarters: 345 East 47 Street, New York, NY 10017. NY Telephone: 212-705 + extension:
`Information -7900; General Manager -7910: Controller -7748; Public Information -7867: Publishing Services -7560: Spectrum -7556; Technical Services -7890. NY
`Telecopier: 212-752-4929. NY Telex: 236-411 (international messages only). IEEE Service Center (for orders, subscriptions, address changes, Educational Activities,
`Region/Section/Student Services, Standards): 445 Hoes Lane , P.O. Box 1331, Piscataway , NJ 08855-1331. NJ Telephone: 201-981-0060. IEEE Washington Office (for
`U.S. professional activities): 1111 19th Street, NW, Suite 608, Washington. DC 20036. Washington Telephone: 202-785-0017. Price/Publication Information: Individual
`copies: IEEE members $10.00 (first copy only), nonmembers $20.00 per copy. (Note: Add $4.00 postage and handling charge to any order from $1.00 to $50.00, including
`prepaid orders .) Member and nonmember subscription prices available on request. Available in microfiche and microfilm. Copyright and Reprint Permissions:
`Abstracting is permitted with credit to the source. Libraries are permitted to photocopy beyond the limits of the U.S. Copyright law for private use of patrons: I) those
`post-1977 articles that carry a code at the bottom of the first page, provided the per-copy fee indicated in the code is paid through the Copyright Clearance Center, 29 Congress
`Street, Salem, MA 01970; 2) pre-1978 articles without fee . Instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. F or
`all other copying, reprint , or republication permission, write to Copyrights and Permissions Department, IEEE Publishing Services, 345 East 47 Street, New York, NY
`10017. Copyright © 1990 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Second-class postage paid at New York, NY. and at
`additional mailing offices. Postmaster: Send address changes to IEEE Transactions on Computers, IEEE, 445 Hoes Lane , P.O. Box 1331, Piscataway , NJ 08855- 133 1.
`
`

`

`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 1, JANUARY 1990
`
`1
`
`Editor's Notice
`
`AS . WE enter the 39th year of publishing the IEEE
`
`TRANSACTIONS ON COMPUTERS (IEEETC), it is appropriate
`to look both backward and forward. The progress in computer
`science and engineering during the past decades is indeed very
`significant. As the oldest archival publication in this field, this
`TRANSACTIONS has published papers in the forefront of com(cid:173)
`puter research. As the field evolves and matures, several
`subfields have emerged. In order to meet the needs of
`researchers in those specialized subfields, the IEEE Computer
`Society has started publication of the following four spin-off
`TRANSACTIONS during the past 15 years:
`1) SOFTWARE ENGINEERING (1975)
`2) PATTERN ANALYSIS AND MACHINE INTELLIGENCE (1980)
`3) KNOWLEDGE AND DATA ENGINEERING (1989)
`4) p ARALLEL AND DISTRIBUTED SYSTEMS (1990).
`As the "father" and "grandfather" of those TRANSACTIONS,
`we will keep publishing papers that deal not only with the
`research areas of current importance to the membership of the
`Society, but also with interdisciplinary areas of emerging
`concerns. In other words, in addition to publishing regular
`papers in the traditional areas , we will continue to publish
`special issues in those areas that may again spin off from this
`TRANSACTIONS in the future. Accordingly, I am very pleased to
`announce the following special issues scheduled for 1990 and
`1991:
`.
`A
`.
`1 1990
`1 T 1
`C
`1) Fau t- o erant omputmg ( pn
`)
`2) ComputerArithmetic(August 1990)
`.
`.
`(A
`il 1991)
`1 E
`3
`) Protoco
`ngmeermg
`pr
`4) Neural Networks (December 1991).
`
`Protocol engineering is concerned with the design and
`implementation of computer-communication protocols. It
`deals with the specification, analysis (validation, verification,
`and performance), synthesis, conversion, adaptation, coding,
`and testing of protocols. It is an interdisciplinary area
`involving computer systems, communication technologies,
`formal theory, software engineering, and artificial intelli(cid:173)
`gence.
`An artificial neural network is a trainable and massively
`parallel computational structure modeled on biological proc(cid:173)
`esses. Neural networks have been applied in many other
`disciplines including vision, speech recognition, and robotics.
`Research in this area includes modeling, design of efficient
`learning algorithms, innovative applications, development of
`simulation/emulation tools, and advanced implementation
`technologies.
`We currently receive about 40 papers per month, not
`counting special issues. The backlog situation has improved
`somewhat due to the 200-page expansion for 1989. Our major
`delay in review is getting reviewers to respond promptly. If
`you are requested by an editor to review a paper, please try to
`get your review back to the editor within one month. If you
`need more time to complete the review, please advise the
`editor; otherwise, please return the package immediately.
`Finally, I should like to acknowledge Prof. M. H. Adb-El-
`Barr as a reviewer for the TRANSACTIONS in 1988; his name was
`h R fi
`· d f
`· d
`L'
`bl' h d · h
`i
`1, ma vertent y om1tte
`1
`rom t e
`e eree 1st pu 1s e m t e
`~f.#,,,~
`f h'
`,
`·- o• ~
`_.\)~ .,.c. ""'
`·
`,iuly issue O t IS TRANSACTIONS.
`"\°f\'--
`~~\J
`,w. Q 'i \;
`G
`\~''
`The first two areas are well known and this TRA~SACTIO~~
`already published many special issues in the past. ~~ '"<>,._~:t
`
`!
`
`Ming T. Liu
`Editor-in-Chief
`
`24
`9 f
`
`f I A~
`
`013 X
`2
`I
`
`5 .
`
`_73
`
`

`

`10
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 1, JANUARY 1990
`
`Addressing, Routing, and Broadcasting in
`Hexagonal Mesh Multiprocessors
`
`MING-SYAN CHEN, MEMBER, IEEE, KANG G. SHIN, SENIOR MEMBER, IEEE, AND DILIP D. KANDLUR
`
`Abstract-A family of 6-regular graphs, called hexagonal
`meshes or H-meshes, is considered as a multiprocessor inter(cid:173)
`connection network. Processing nodes on the periphery of an
`H-mesh are first wrapped· around to achieve regularity and ho(cid:173)
`mogeneity. The diameter of a wrapped H-mesh is shown to be
`of O(p112 ), where p is the number of nodes in the H-mesh. An
`elegant, distributed routing scheme is developed for wrapped H(cid:173)
`meshes so that each node in an H-mesh can compute shortest
`paths from itself to any other node with a straightforward al(cid:173)
`gorithm of 0( 1) using the addresses of the source-destination·
`pair only, i.e., independent of the network's size. This is in
`sharp contrast with those previously known algorithms that rely
`on using routing tables. Furthermore, we also develop an ef(cid:173)
`ficient point-to-point broadcasting algorithm for the H-meshes
`which is proved to be optimal in the number of required com(cid:173)
`munication steps.
`The wrapped H-meshes are compared against some other ex(cid:173)
`isting multiprocessor interconnection networks, such as hyper(cid:173)
`cubes, trees, and square meshes. The comparison reinforces the
`attractiveness of the H-mesh architecture.
`
`Index Terms-Addressing and routing strategies, hexagonal
`mesh, interconnectiQn networks, node homogeneity and regu(cid:173)
`larity, regular graphs.
`
`l. INTRODUCTION
`
`MULTIPROCESSOR interconnection networks are often
`
`required to connect thousands of homogeneously repli(cid:173)
`cated processor-memory pairs [1], [2], each of which is called
`a processing node (PN). Instead of using a shared memory,
`all synchronization and communication between PN's for pro(cid:173)
`gram execution is often done via message passing. Design and
`use of multiprocessor interconnection networks have recently
`drawn considerable attention due to the availability of inex(cid:173)
`pensive, powerful microprocessors and memory chips [3]-[6].
`The homogeneity of PN's and the interconnection network is
`very important because it allows for cost/performance bene(cid:173)
`fits from the inexpensive replication of multiprocessor com(cid:173)
`ponents. (See [7]-[9] for more justifications.) Each PN in the
`multiprocessor is preferred to have fixed connectivity so that
`standard VLSI chips can be used. Also, the interconnection
`network needs to contain a reasonably high degree of redun-
`
`Manuscript received June 15, 1987; revised December 30, 1987. This
`work was supported in part by the Office of Naval Research under Con(cid:173)
`tracts N00014-87-G-0086 and N00014-85-K-0122. Any opinions, findings,
`and recommendations expressed in this paper are those of the authors and do
`not necessarily reflect the view of the ONR.
`M.-S. Chen is with IBM Thomas J. Watson Research Center, Yorktown
`Heights, NY 10598.
`K. G. Shin and D. D. Kandlur are with the Real-Time Computing
`Laboratory, Department of Electrical Engineering and Computer Science,
`The University of Michigan, Ann Arbor, MI 48109.
`IEEE Log ·Number 8931922.
`
`dancy so that alternative routes can be made available to detour
`faulty nodes/links. More importantly, the interconnection net(cid:173)
`work must facilitate efficient routing and broadcasting so as
`to achieve high performance in job executions.
`Various research and development results on how to inter(cid:173)
`connect multiprocessor components have been reported in the
`literature [10], [11], [9], [12], [13]. Some of them have been
`compared to each other [3], [14]. However, most of them
`are not satisfactory mainly due to their inability of providing
`al I the following features: the simplicity of interconnection,
`the efficiency of message routing and broadcasting, a fine
`scalability, 1 and a high degree of fault tolerance.
`/
`In this paper, hexagonal meshes (or H-meshes) are pre(cid:173)
`sented as a candidate multiprocessor architecture that pos(cid:173)
`sesses all the foregoing salient features. A large number of
`data manipulation applications require the PN's on the hexag(cid:173)
`onal periphery to be wrapped around to achieve regularity and
`homogeneity such that identical software and protocols can
`be applied uniformly over the network. From a topological
`point of view, the way of wrapping determines the type of
`H-mesh. For example, Martin proposed a general method for
`forming a "boundary-less" topology for a large, dense, and
`regular arrangement of processor and memory modules on
`a two-dimensional surface, called a processing surf ace [15].
`He showed specifieally how to form such a topology on a
`square mesh and implied, without any elaboration, that a sim(cid:173)
`ilar approach could be applied to different processing surfaces.
`Stevens illustrated an interesting way of wrapping H-meshes
`of size less than or equal to three, where the size of an H-mesh
`is defined as the number of nodes on each peripheral edge of
`the H-mesh [9]. His method for addressing, message routing,
`and broadcasting in H-meshes, however, is very complex and
`inefficient.
`To the best of our knowledge, there is no general efficient
`method for wrapping, routing, and broadcasting in H-meshes
`known to date. Consequently, in this paper, a method for sys(cid:173)
`tematically wrapping H-meshes of arbitrary size is presented,
`and a new, simple addressing scheme for the H-meshes is
`proposed. Then, efficient routing and broadcasting algorithms
`under the new addressing scheme are developed. As we shall
`see, the proposed addressing scheme not only achieves the
`homogeneity of PN's but also facilitates routing and broad(cid:173)
`casting in th~ H-meshes significantly.
`The rest of this paper is organized as follows. In Section
`
`1 Scalability is measured in terms of the number of PN's necessary to in(cid:173)
`crease the network's dimension by one.
`
`0018-9340/90/0100-0010$01.00 © 1990 IEEE
`
`

`

`CHEN et al.: ADDRESSING, ROUTING , AND BROADCASTING IN HEXAGONAL MESH MULTIPROCESSORS
`
`11
`
`Fig. 1. A regular nonhomogeneous graph.
`
`Row
`
`1 z
`
`Fig. 2. An H-mesh of size 3 without wrapping.
`
`II, a systematic way to wrap the fl-mesh, called the con(cid:173)
`tinuous type (C-type) wrapping, is presented as a means of
`achieving the regularity and the homogeneity of PN' s. Topo(cid:173)
`logical properties of fl-meshes are explored in Section III.
`In light of these properties , an addressing scheme for a C(cid:173)
`type wrapped fl-mesh is proposed in Section IV. With that
`addressing scheme, efficient routing and broadcasting algo(cid:173)
`rithms are then developed. In Section V, we compare the C(cid:173)
`type wrapped fl-meshes with some other existing multiproces(cid:173)
`sor structures, such as hypercubes, trees, and square meshes.
`The paper concludes with Section VI.
`
`II. SYSTEMATIC WRAPPING OF fl-MESHES
`A graph is said to be regular if all the nodes in the graph
`have the same degree, and homogeneous if all the nodes in
`that graph are topologically identical. Clearly, homogeneity
`implies regularity, but the converse does not always hold. For
`example, the graph in Fig. 1 is regular, but not homogeneous
`since node x and node y are not topologically identical. The
`degree of all nodes in an fl-mesh without wrapping, except
`those on its periphery, is 6. Thus, such an fl-mesh is neither
`homogeneous nor regular. Fig. 2 illustrates an unwrapped fl(cid:173)
`mesh of size 3.
`Consider the central node of the fl-mesh in Fig. 3. The
`node has six oriented directions, each of which leads to one
`of its six nearest neighbors. Without loss of generality, any
`of the six directions can be defined as the x direction, the
`direction 60 degrees clockwise to the x direction as the y di(cid:173)
`rection , and then the direction 60 degrees clockwise to they
`direction as the z direction. Once the x, y, and z directions
`are defined, an fl-mesh of size n can be partitioned into 2n -1
`rows with respect to any of these three directions; there are
`three different ways of partitioning the rows of an fl-mesh.
`Fig. 3 shows the rows in an fl-mesh of size 3 which are parti(cid:173)
`tioned with respect to the x , y, and z directions, respectively.
`To facilitate our presentation, when an H-mesh of size n is
`partitioned into 2n - 1 rows with respect to any of the three
`
`Row 3Y
`Fig. 3. Partitioned rows of an H 3 in x , y, and z directions.
`
`directions, and the fl-mesh is rotated in such a way that the
`corresponding direction from the central node points to the
`right, the top row is referred to as row O in that direction,
`the second to the top row is referred to as row 1, and so on.
`Also, row n - l is called the central row and rows O to n - 2
`and rows n to 2n - 2 will sometimes be referred to as the
`upper and lower parts of an fl-mesh of size n, respectively.
`(Subscripts for the row numbers in Fig. 3 are used to indicate
`their directions.)
`For notational simplicity, let [ b ]a = b mod a, for all a E J+
`and b E /, where I is the set of integers and J+ the set of posi(cid:173)
`tive integers. To make the fl-mesh homogeneous and regular,
`the following method for wrapping an H-mesh continuously,
`called the C-type wrapping, is proposed.
`.
`.
`C-type wrapping:. Wrap an fl-mesh of size n m such a
`way that for each of the three ways of partitioning the PN's
`into rows, the last PN in the row i is connected to the first
`PN of row [i + n - lhn-1 ·
`As will be stateq later in Corollary 1. 1, the PN's in an
`fl-mesh with the C-type wrapping are homogeneous. Fur(cid:173)
`thermore, the C-type wrapping allows for an easy addressing
`scheme and, thus, simplifies the routing and broadcasting in
`an H-mesh significantly. In what follows, an H-mesh of size n
`with the C-type wrapping is denoted by Hn, while that without
`wrapping is denoted by H~.
`The edges in the rows partitioned with respect to the x
`(y or z) direction and the associated wrapping are called the
`edges in the x (y or z) direction. An illustrative example of
`partitioning edges in an fl3 into three different directions is
`given in Fig. 4, where the edges in each direction are drawn
`separately for clarity. From Figs. 3 and 4, it can be observed
`that there is a unique path from one node to another in an Hn
`along each of the three directions.
`III. TOPOLOGICAL PROPERTIES OF HEXAGONAL MESHES
`The following two lemmas are direct results of the structure
`of an fl-mesh .
`Lemma 1: The number of nodes in an Hn is p = 3n2 -
`3n + l.
`
`

`

`12
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO . 1, JANUARY 1990
`
`(15,6, 10)
`0
`
`(16, 14, 17)
`0
`
`(8,7,18)
`0
`
`(9,15 ,6)
`0
`(2,16 ,1 4)
`0
`
`(1,8,7)
`0
`
`(0,0,0)
`0
`
`(14, 17,3)
`0
`(7,18,11)
`(6,10,4)
`0
`0
`(18, 11, 12)
`0
`(11,12,1)
`0
`
`( 17,3,5)
`0
`(10,4,13)
`0
`
`(12,1,8)
`0
`
`(13,9,15)
`0
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 4. An H 3 with the C-type wrapping. (a) Edges in the x-direction. (b)
`Edges in they-direction. (c) Edges in the z- direction .
`
`Proof· Since there are always n +i nodes in row i as well
`as in row 2n -i -2 for O::; i ::; n -2, and 2n-1 nodes in row
`n -1, the desired result follows from ~'?:o2 2(n +i) + 2n -1 =
`l)(n -2) +2n -1 = 3n2 -3n + 1. Q.E.D.
`2n(n -1) +(n -
`Lemma 2: The sum of the number of nodes in row i and
`that of row i + n is 3n - 2 for O ::; i ::; n -:- 2.
`The proof of Lemma 2 is trivial and, thus, omitted.
`To exploit the topological properties of an Hn , each node
`is labeled with a 3-tuple as follows. Start from the central
`node of the Hn and label that node with (0, 0, 0), where the
`first coordinate of a node is referred to as its x labeling and
`
`(5,2, 16)
`(4, 13,9)
`(3,5,2)
`0
`0
`0
`Fig. 5. An H3 with a 3-tuple labeling.
`
`the second and third coordinates are referred to as its y and
`z labelings, respectively. Then, move to the next node along
`the x direction, assign that node the x labeling one more than
`that of its preceding node, and so on. They and z labelings
`for each node are determined by moving along the y and z
`directions, respectively, instead of the x direction. An example
`of the 3-tuple labeling of an H3 is given in Fig. 5, where the
`edges are not drawn for clarity.
`Theorem 1: Let (x1, Y1, z1) and (x2, Y2, z2) be, respec(cid:173)
`tively, the labelings of nodes n 1 and n2 in an Hn and p
`3n2
`- 3n + 1. Then,
`a) [x2 - xt]p = [(3n2
`- 6n + 3)(Y2 - Y1)]p.
`b) [x2 - xi]p = [(3n2 - 6n + 2)(z2 - z1)]p.
`Proof For any pair of adjacent nodes nu and nu in the
`y-direction, respectively, with the labelings (Xu, y, Zu) and
`(Xu, [y+l]p, Zu), we want to claim [Xu-Xu]p = 3n 2 -6n+3.
`We shall prove this claim first and then a) follows immediately
`from the claim.
`Consider a path P* from nu to nu following the +x di(cid:173)
`rection only. (As can be seen in Fig. 4(a), such a path is
`unique.) Suppose nu is in row r u according to the row par(cid:173)
`tition with respect to the x direction. Recall that the C-type
`wrapping requires the end of a row to be connected to the
`beginning of a row that is n - 1 rows away from it. Since
`[(n - 1)(2n - 3)]~n-l = 1, P* must run through nodes in
`2n - 2 different rows to get from nu to nu-which are ad(cid:173)
`jacent in the y direction- including the rows that contain nu
`and nu. In other :words, the path P* must visit all but
`1) those node§ ahead of nu in row r u, ·
`2) those nodes behind nu in row [ru + lhn-1, and
`3) those nodes in row [ru + nhn-1 (the only row that P*
`does not travel).
`Note that if nu is in the upper part or central row of an Hn,
`the total number of nodes in 1) and 2) will be one less than
`the number of nodes in row r u. On the other hand, if nu is
`in the lower part of the Hn, the total number of nodes in
`1) and 2) will be one less than the number of nodes in row
`[r u + l hn -1 . By Lemma 2, we conclude that for both cases,
`the total number of nodes in 1), 2), and 3) is 3n - 3, i.e.,
`one less than 3n - 2. Thus, the number of nodes on P * is
`(3n - 3) = 3n 2
`(3n 2
`- 3n + 1) -
`- 6n + 4. Since both nu
`and nu are ~ontained in P *, the claim is thus proved and a)
`follows.
`For b), we claim that for any pair of adjacent nodes nu and
`nu in the z direction labeled, respectively, with (Xu, Yu, z)
`and (Xu, Yu, [z + l]p), [Xu -Xu]p = 3n2 -6n +2. This claim
`can be proved by following the same logic as above and, thus,
`b) can be proved similarly.
`Q.E.D.
`
`

`

`CHEN et al.: ADDRESSING, ROUTING, AND BROADCASTING IN HEXAGONAL MESH MULTIPROCESSORS
`
`13
`
`18
`
`0
`
`4
`
`Fig. 6. A redrawn H3.
`Note that (3n 2 - 3n + 1) -
`- 6n + 2) = 3n - 1,
`(3n 2
`(3n2 -3n + 1)-(3n2 -6n +3) = 3n -2. In light of Theorem
`1, an Hn can be redrawn as a power cycle with p = 3n2 -
`3n + 1 nodes, in which node i is not only adjacent to nodes
`l]p and [i + l]p, but also adjacent to nodes [i + 3n - l]p,
`[i -
`[i + 3n - 2]p, [i + 3n2 - 6n + 2]p, and [i + 3n2 - 6n + 3]p.
`For example, an H 3 can be redrawn as the one in Fig. 6. This
`fact leads to the following corollary.
`Corollary 1.1: All the processing nodes in an Hn are ho(cid:173)
`mogeneous.
`Note that, although extensive results have been obtained for
`many classes of networks [16]-[19], the connection pattern in
`an H-mesh does not belong to any of the previously found
`patterns.
`Lemma 3:
`a) The number of links in an H~ is 9n2 -
`l5n + 6.
`b) The number of links in an Hn is 9n2 - 9n + 3.
`Proof: We prove b) first. From the fact that the sum(cid:173)
`mation of all node degrees in a graph is twice the number of
`edges in that graph, we have 6(3n2 -3n + 1)/2 = 9n 2 -9n +3.
`Since there are 6(n - 1) nodes in the periphery of an H~,
`six of which have degree 3 and 6n - 12 of which have degree
`4, we have the summation of all node degrees in an H~:
`6(3n2 -3n+l-6n+6)+6 x 3+(6n-12)4 = 18n2 -30n+12,
`making the number of links in an H~ equal to 9n2 -
`l5n + 6.
`Q.E.D.
`Lemma 4:
`a) The diameter of an Hn is n - l.
`b) The average distance in an Hn is (2n - 1)/3.
`Proof· a) follows from the fact that, without loss of gen(cid:173)
`erality, every node in a wrapped H-mesh can view itself as the
`central node of the mesh. To prove b), let td(Hn) denote the
`summation of distances from any node to all the other nodes
`in an Hn. Then,
`
`1~ 2n -
`
`l) = n(n -
`
`l)(2n - 1).
`
`n-1
`td(Hn) = L6d2 = 6n(n -
`d = l
`The average distance is thus td(H n) / (p - 1) = (2n - 1) /3.
`Q.E.D.
`Moreover, Lemma 1 and a) of Lemma 4 lead to the follow(cid:173)
`ing lemma.
`
`30
`
`31
`
`32
`
`33
`
`19
`
`20
`
`21
`
`22
`
`23
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`34
`
`35
`
`36
`
`0
`
`1
`
`2
`
`3
`
`24
`
`25
`
`26
`
`27
`
`28
`
`29
`
`0 0 0 0
`0 0 0 0 0
`0 0 0 0 0 0
`0 0 0 0 0 0 0
`0 0 0000
`0 0 0 0 0
`6
`0 0 0 0
`(a)
`
`14
`
`15
`
`16
`
`17
`
`18
`
`4
`
`5
`
`7
`
`4
`
`5
`
`6
`
`30
`
`31
`
`32
`
`33
`
`34
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`35
`
`36
`
`0
`
`1
`
`2
`
`3
`
`0 0 0 0
`0 0 0 0 0
`0 0 0 0 0 0
`0 0 0 0 0 0 0
`000000
`0 0 0 0 0
`0 0 0 0
`(b)
`Fig. 7. An illustrative example of Theorem 2. (a) An H4. (b) An H 4( II ) ·
`
`25
`
`26
`
`27
`
`28
`
`29
`
`15
`
`16
`
`17
`
`18
`
`Lemma 5: The diameter of an H-mesh withp nodes grows
`as O(p112 ).
`In addition, it is worth mentioning that H-meshes possess
`a high degree of fault tolerance measured in terms of con(cid:173)
`nectivity. Recall that a graph is said to be m-connected (m(cid:173)
`edge connected) if ,n is the minimal number of nodes (edges)
`whose removal will disconnect the graph [5]. It can be easily
`verified that an H-mesh of any size is 6-connected and also
`6-edge connected. This means that an H-mesh can tolerate up
`to five node/link failures at a time, which is better than most
`of the other existing networks [ 14], [20].
`
`IV. ROUTING AND BROADCASTING IN H-MESHES
`In this section, a simple addressing scheme for H-meshes
`is developed on the basis of the C-type wrapping. Under this
`addressing scheme, shortest paths from one node to any other
`node can be computed by the source node with an extremely
`simple algorithm of 0(1). A point-to-point broadcasting algo(cid:173)
`rithm is also developed, which is proved to be optimal in the
`number of required communication steps.
`
`A. Addressing Scheme
`Using Theorem 1, the y and z labels of any node can be
`obtained from1 its x label, meaning that only one (instead of
`three) label will suffice to uniquely identify any node in an H(cid:173)
`mesh. An example of this addressing for an H 4 is given in Fig.
`7(a) where all edges are omitted for clarity. This addressing
`scheme is much simpler than the one in [9], since only one
`number, instead of two, is needed to identify each node in an
`Hn. Furthermore, the routing strategy under this addressing
`
`

`

`14
`
`scheme will be shown to be far more efficient than the one
`in [9], especially when messages must be routed via wrapped
`links.
`
`B. Routing
`Under the above addressing scheme, a shortest path between
`any two nodes can be easily determined from the difference
`of their addresses.
`Let mx, my, and mz be, respectively, the number of moves
`or hops from the source node to the destination node along the
`x, y, and z directions on a shortest path. Negative values mean
`the moves are in opposite directions. Note that there could be
`several equally short paths from a node to another, and these
`shortest paths are completely specified by the values of mx,
`my, and mz. More precisely, it can be verified that for i =
`x, y, z, the number of paths with mi moves in the correspond(cid:173)
`ing directions is (lmx I+ lmy I+ lmz l)!/(lmx I! lmy I! lmz I!). Let
`sand d be, respectively, the addresses of the source and des(cid:173)
`tination nodes, and k = [d - s]p where p = 3n2 - 3n + 1.
`Then, the mx, my, and mz for shortest paths from s to d can
`be determined by the algorithm given below.
`Algorithm A 1:
`begin
`mx := O; my := O; mz := O;
`if (k < n) then begin mx := k; stop end;
`if (k > 3n2 -4n + 1) then begin mx := k -3n 2 +3n -1;
`stop end;
`r := (k - n) div (3n - 2);
`t := (k - n) mod (3n - 2);
`if ( t ::; n + r - 1)
`then /* d is in the lower part of the H-mesh centered at
`s. * I
`if (t ::; r)
`then mx := t - r; mz := n - r -
`l;
`else if (t 2: n - 1) then m x : = t - n + 1; my : =
`n - r - 1;
`else my : = t - r; m z : = n -
`endif;
`endif;
`else /* dis in the upper part of the H-mesh centered at
`s. * I
`if (t ::; 2n - 2)
`then mx := t + 2 - 2n; my:= -r - 1;
`else if (t 2: 2n +r -1) then mx := t -2n -r + 1;
`mz := -r -1;
`else my := t + 1 - 2n - r; mz : = 2n - t - 2;
`endif;
`endif;
`endif;
`stop
`end;
`The correctness of A I is proved by the theorem below.
`Theorem 2: The values of mx, my, and mz determined by
`A I completely specify all the shortest paths from s to d in an
`Hn.
`
`t - 1 ;
`
`Proof: By Theorem 1, without loss of generality the
`source node can view itself as the central node of the Hn.
`Let H n(s) be the H-mesh centered at s. For the case when dis
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. I, JANUARY 1990
`
`in the central row (i.e., row n -1) of Hn(s), mx is determined
`by the statements in lines 2 and 3 of A 1 , and my = m z = 0.
`Consider the case when dis in a row other than row n -1 of
`H n(s). Form a group of nodes with the nodes of rows n -i - 2
`and 2n -i -2; call this group i. Then, in Fig. 3, rows 1 and
`4 form group 0, and rows O and 3 form group 1. A group
`consists of two rows, one from the upper part and the other
`from the lower part of H n(s) . We know from Lemma 2 that
`each group contains 3n - 2 nodes. Then, by the statements in
`lines 5 and 6 of A 1 , r is determined as the identity of the group
`which contains d in H n(s), and t is the position of d in group
`r. We can determine from t which row of Hn(s) contains d.
`Denote the first node of that row by n1. A shortest path from
`s to n1 and that from n1 to d can thus be determined. Using
`the idea of the composition of vectors, we get the desired
`equations for mx, my, and mz. Q.E.D.
`An illustrative example for routing in an H 4 is given in
`Fig. 7 where edges are omitted for clarity. Suppose node 11
`sends a message to node 5, i.e., n = 4, s = 11, d = 5, and
`k = [5-11]37 = 31. The original H 4 is given in Fig. 7(a) and
`H 4(1l) is in Fig.