Page last updated on 2024 March 22

*Enrollment code:* 13011

*Prerequisite:* ECE 254A (can be waived, but ECE 154B is required)

*Class meetings:* MW 10:00-11:00, Phelps 1431 (inverted classroom)

*Instructor:* Professor Behrooz Parhami

*Open office hours:* MW 11:00-11:45, Phelps 1431

**Course announcements:** Listed in reverse chronological order

**Course calendar:** Schedule of lectures, homework, exams, research

**Homework assignments:** Five assignments, worth a total of 40%

**Exams:** None for winter 2024

**Research paper and poster:** Worth 60%

**Research paper guidlines:** Brief guide to format and contents

**Poster presentation tips:** Brief guide to format and structure

**Policy on academic integrity:** Please read very carefully

**Grade statistics:** Range, mean, etc. for homework and exam grades

**References:** Textbook and other sources (Textbook's web page)

**Lecture slides:** Available on the textbook's web page

**Miscellaneous information:** Motivation, catalog entry, history

Discussion sessions, homework assignments, and research milestones are scheduled as follows (lectures have been pre-recorded, so class sessions will be devoted to discussion and Q&A). This schedule will be strictly observed. In particular, no extension is possible for homework due dates; please start work on the assignments early. Each lecture covers topics in 1-2 chapters of the textbook. Chapter numbers are provided in parentheses, after day & date. PowerPoint and PDF files of the lecture slides can be found on the textbook's web page.

**Day & Date (book chapters) Lecture topic [HW posted/due] {Research milestones}**

M 01/08 (1) Lecture 1 Introduction to parallel processing

W 01/10 Bonus introductory lecture: Start watching from the 20:50 mark of this 100-minute video

M 01/15 No lecture: Martin Luther King Holiday [HW1 posted; chs. 1-4]

W 01/17 (2) Lecture 2 A taste of parallel algorithms

M 01/22 (3-4) Lecture 3 Complexity and parallel computation models {Research topics announced}

W 01/24 (5) Lecture 4 PRAM shared-memory model & algorithms [HW1 due] [HW2 posted; chs. 5-6C]

M 01/29 Special lecture (0:06:00-1:07:06): Interconnection Networks for Parallel Processors & Data Centers

W 01/31 (6A) Lecture 5 More shared-memory algorithms {Research preferences due; topics assigned

M 02/05 (6B-6C) Lecture 6 Shared-memory impl'ns & abstractions [HW2 due] [HW3 posted; chs. 7-8C]

W 02/07 (7) Lecture 7 Sorting and selection networks

M 02/12 (8A) Lecture 8 Search acceleration circuits

W 02/14 (8B-8C) Lecture 9 Other circuit-level examples [HW3 due]

M 02/19 No lecture: President's Day Holiday [HW4 posted; chs. 9-12]

W 02/21 (9) Lecture 10 Sorting on a 2D mesh/torus architectures {Preliminary references due}

M 02/26 (10) Lecture 11 Routing on a 2D mesh/torus architectures

W 02/28 (11-12) Lecture 12 Other mesh/torus concepts

M 03/04 (13) Lecture 13 Hypercubes and their algorithms [HW4 due] [HW5 posted; chs. 13-16]

W 03/06 (14) Lecture 14 Sorting and routing on hypercubes

M 03/11 (15-16) Lecture 15 Other interconnection architectures {Final ref's & provisional abstract due}

W 03/13 (17) Lecture 16 Network embedding and task scheduling [HW5 due]

W 03/20 {Research paper PDF file due by midnight}

T 03/26 {Course grades due by midnight}

- Because solutions will be handed out on the due date, no extension can be granted.

- Include your name, course name, and assignment number at the top of the first page.

- If homework is handwritten and scanned, make sure that the PDF is clean and legible.

- Although some cooperation is permitted, direct copying will have severe consequences.

** Homework 1: Introduction, complexity, and models** (Chs. 1-4; due W 2024/01/24, 10:00 AM)

Do the following problems from the textbook: 1.7, 1.11, 2.9, 3.5, 3.7cd, 4.5

** Homework 2: Shared-memory parallel processing** (Chs. 5-6C; due M 2024/02/05, 10:00 AM)

Do the following problems from the textbook: 5.2, 5.4, 5.12, 6.3, 6.13, 16.13 (not a typo!)

** Homework 3: Circuit model of parallel processing** (Chs. 7-8C; due W 2024/02/14, 10:00 AM)

Do the following problems from the textbook: 7.4, 7.7, 7.9, 8.6, 8.9, 8.13

** Homework 4: Mesh/torus-connected parallel computers** (Chs. 9-12; due M 2024/03/04, 10:00 AM)

Do the following problems from the textbook: 9.3, 9.9, 10.5, 11.2, 11.5, 12.2

** Homework 5: Hypercubic & other parallel computers** (Chs. 13-16; due W 2024/03/13, 10:00 AM)

Do the following problems from the textbook: 13.3, 13.8, 14.4, 14.10, 15.7, 16.2

The following sample exams using problems from the textbook are meant to indicate the types and levels of problems, rather than the coverage (which is outlined in the course calendar). Students are responsible for all sections and topics, in the textbook, lecture slides, and class handouts, that are not explicitly excluded in the study guide that follows the sample exams, even if the material was not covered in class lectures.

** Sample Midterm Exam (105 minutes)** (Chapters 8A-8C do not apply to this year's midterm)

Textbook problems 2.3, 3.5, 5.5 (with

*Midterm Exam Study Guide*

The following sections are excluded from Chapters 1-7 of the textbook to be covered in the midterm exam, including the three new chapters named 6A-C (expanding on Chpater 6):

3.5, 4.5, 4.6, 6A.6, 6B.3, 6B.5, 6C.3, 6C.4, 6C.5, 6C.6, 7.6

** Sample Final Exam (150 minutes)** (Chapters 1-7 do not apply to this year's final)

Textbook problems 1.10, 6.14, 9.5, 10.5, 13.5a, 14.10, 16.1; note that problem statements might change a bit for a closed-book exam.

*Final Exam Study Guide*

The following sections are excluded from Chapters 8A-19 of the textbook to be covered in the final exam:

8A.5, 8A.6, 8B.2, 8B.5, 8B.6, 9.6, 11.6, 12.5, 12.6, 13.5, 15.5, 16.5, 16.6, 17.1, 17.2, 17.6, 18.6, 19

Our textbook covers some general ideas on interconnection networks in Chapter 16 and many example networks throughout the book. In addition, you will find the first two of the following references useful. The first one has good theoretical coverage, while the second one focuses on networks used in actual top-of-the-line supercomputers. The third reference is listed for its relative recency.

[Xu13] J. Xu, *Topological Structure and Analysis of Interconnection Networks*, Springer, 2013.

[Trob16] R. Trobec, R. Vasiljevic, M. Tomasevic, V. Milutinovic, R. Beivide, and M. Valero, "Interconnection Networks in Petascale Computer Systems: A Survey," *ACM Computing Surveys*, Vol. 49, No. 3, pp. 1-24, 2016.

[Moud21] M. Moudi and M. Othman, "A Survey on Emerging Issues in Interconnection Networks," *Int'l J. Internet Technology and Secured Transactions*, Vol. 11, No. 2, pp. 131-159, 2021.

Here is a list of research paper titles, presented in five sections. Sample references follow the titles to help define the scope and serve as starting points.

For topic selection, you should give me your first to fourth choices among the topics that follow by the "Research topic preferences due" deadline. I will then assign a topic to you within a few days, based on your preferences and those of your classmates. Each preference should be presented in the following format (shown for someone's third choice):

(3) D2. Fault-Diameter of Interconnection Networks

Please include both the topic's two-character code and its full title, as it is quite easy to commit a typo in the code and end up with a wrong topic.

**Dependability Attributes**

D1. Node- and Edge-Connectivity of Networks (Not available for winter 2024)

[Gutm06] I. Gutman and S. Zhang, "Graph Connectivity and Wiener Index," *Bulletin* (Academie Serbe des Sciences et des Arts. Classe des Sciences Mathematiques et Naturelles. Sciences mathematiques), pp. 1-5, 2006.

[Wigd92] A. Wigderson, "The Complexity of Graph Connectivity," *Proc. Int'l Symp. Mathematical Foundations of Computer Science*, Springer, pp. 112-132, 1992.

D2. Fault-Diameter of Interconnection Networks (Assigned to: **Hejia Geng**)

[Kris87] M. S. Krishnamoorthy and B. Krishnamurthy, "Fault Diameter of Interconnection Networks," *Computers & Mathematics with Applications*, Vol. 13, Nos. 5-6, pp. 577-582, 1987.

[Xu02] J.-M. Xu and X. Xie, "On Fault-Tolerant Diameter and Wide Diameter of Graphs," *J. University of Science and Technology of China*, Vol. 32, No. 2, pp. 135-139, 2002.

D3. Wide-Diameter of Interconnection Networks (Assigned to: **TBD**)

[Xu02] J.-M. Xu and X. Xie, "On Fault-Tolerant Diameter and Wide Diameter of Graphs," *J. University of Science and Technology of China*, Vol. 32, No. 2, pp. 135-139, 2002.

[Gao15] S. Gao and C. Zhu, "Wide Diameter for Two Families of Interconnection Networks," *Wuhan University J. Natural Sciences*, Vol. 20, No. 5, pp. 375-380, 2015.

D4. Parallel Disjoint Paths in Networks (Assigned to: **TBD**)

[Iqba15] F. Iqbal and F. A. Kuipers, "Disjoint Paths in Networks," *Wiley Encyclopedia of Electrical and Electronics Engineering*, 2015.

[Ling14] S. Ling and W. Chen, "Node-to-Set Disjoint Paths in Biswapped Networks," *The Computer J.*, Vol. 57, No. 7. pp. 953-967, 2014.

D5. Modeling of Interconnection Network Reliability (Assigned to: **TBD**)

[Dash12] R. K. Dash, N. K. Barpanda, P. K. Tripathy, and C. R. Tripathy, "Network Reliability Optimization Problem of Interconnection Network Under Node-Edge Failure Model," *Applied Soft Computing*, Vol. 12, No. 8, pp. 2322-2328, 2012.

[MdYu16] N. A. Md Yunus, M. Othman, Z. Mohd Hanapi, and K. Y. Lun, K.Y., "Reliability Review of Interconnection Networks," *IETE Technical Review*, Vol. 33, No. 6, pp. 596-606, 2016.

D6. Dependability Assessment via Resistance Distance in Networks (Not available for winter 2024)

[Klei93] D. J. Klein and M. Randic, "Resistance Distance," *J. Mathematical Chemistry*, Vol. 12, No. 1, pp. 81-95, December 1993.

[Tizg10] A. Tizghadam and A. Leon-Garcia, "Betweenness Centrality and Resistance Distance in Communication Networks," *IEEE Network*, Vol. 24, No. 6, pp. 10-16, November 2010.

D7. Reliability Inversion in Network Evaluation (Assigned to: **TBD**)

[Parh20] B. Parhami, "Reliability Inversion: A Cautionary Tale," *IEEE Computer*, Vol. 53, No. 6, pp. 28-33, June 2020.

[Cama88] P. Camarda and M. Gerla, "Reliability Comparison of Computer Networks," *Proc. IEEE INFOCOM Conf.*, 1988, pp. 835-841.

[Yunu16] N. A. M. Yunus, M. Othman, Z. M. Hanapi, and K. Y. Lun, "Reliability Review of Interconnection Networks," *IETE Technical Review*, Vol. 33, No. 6, 2016, pp. 596-606.

**Network Classes**

N1. Swapped and Biswapped Networks (Not available for winter 2024)

[Yeh96] C. H. Yeh and B. Parhami, "Swapped Networks: Unifying the Architectures and Algorithms of a Wide Class of Hierarchical Parallel Processors," *Proc. Int'l Conf. Parallel and Distributed Systems*, pp. 230-237, 1996.

[Xiao11] W. Xiao, B. Parhami, W. Chen, M. He, and W. Wei, "Biswapped Networks: A Family of Interconnection Architectures with Advantages over Swapped or OTIS Networks," *Int'l J. Computer Mathematics*, Vol. 88, No. 13, pp. 2669-2684, 2011.

N2. Constant-Diameter Networks (Assigned to: **Hunter Larson**)

[Parh05] B. Parhami and M. Rakov, "Perfect Difference Networks and Related Interconnection Structures for Parallel and Distributed Systems," *IEEE trans. Parallel and Distributed Systems*, Vol. 16, No. 8, pp. 714-724, 2005.

[Kita16] T. Kitasuka and M. Iida, "A Heuristic Method of Generating Diameter 3 Graphs for Order/Degree Problem," *Proc. 10th IEEE/ACM Int'l Symp. Networks-on-Chip (NOCS)*, pp. 1-6, 2016.

N3. Chordal-Ring Networks (Assigned to: **TBD**)

[Bujn03] S. Bujnowski, B. Dubalski, and A. Zabludowski, "Analysis of Chordal Rings," *Mathematical Techniques and Problems in Telecommunications*, pp. 257-279, 2003.

[Parh99] B. Parhami and D.-M. Kwai, "Periodically Regular Chordal Rings," *IEEE Trans. Parallel and Distributed Systems*, Vol. 10, No. 6, pp. 658-672, 1999.

N4. Low- vs. High-Dimensional Mesh Networks (Assigned to: **Kedai Zuo**)

[Dall90] W. J. Dally, "Performance Analysis of k-ary n-cube Interconnection Networks," *IEEE Trans. Computers*, Vol. 39, No. 6, pp. 775-785, 1990.

[Parh04] B. Parhami and D. M. Kwai, "Comparing Four Classes of Torus-Based Parallel Architectures: Network Parameters and Communication Performance," *Mathematical and Computer Modelling*, Vol. 40, Nos. 7-8, pp. 701-720, 2004.

N5. Variations on the Fat-Tree Network (Assigned to: **TBD**)

[Jain17] N. Jain, A. Bhatele, L. H. Howell, D. Bohme, I. Karlin, E. A. Leon, M. Mubarak, N. Wolfe, T. Gamblin, and M. L. Leininger, "Predicting the Performance Impact of Different Fat-Tree Configurations," *Proc. Int'l Conf. High Performance Computing, Networking, Storage and Analysis*, pp. 1-13, 2017.

[Wang12] Z. Wang, J. Xu, X. Wu, Y. Ye, W. Zhang, M. Nikdast, X. Wang, and Z. Wang, Z., "Floorplan Optimization of Fat-Tree-Based Networks-on-Chip for Chip Multiprocessors," *IEEE Trans. Computers*, Vol. 63, No. 6, pp. 1446-1459, 2012.

N6. Performance Implications of Network Pruning (Not available for winter 2024)

[Kwai04] D. M. Kwai and B. Parhami, "Incomplete *k*-ary *n*-cube and its Derivatives," *J. Parallel and Distributed Computing*, Vol. 64, No. 2, pp. 183-190, February 2004.

[Stew13] I. A. Stewart, "Interconnection Networks of Degree Three Obtained by Pruning Two-Dimensional Tori," *IEEE Trans. Computers*, Vol. 63, No. 10, pp. 2473-2486, July 2013.

N7. Periodically-Regular Perfect Difference Networks (Assigned to: **Minh Bui**)

[Parh99] B. Parhami and D.-M. Kwai, "Periodically Regular Chordal Rings," *IEEE Trans. Parallel and Distributed Systems*, Vol. 10, No. 6, 1999, pp. 658-672. (Printer's errors corrected in: Vol. 10, No. 7, 1999, pp. 767-768.)

[Parh05] B. Parhami and M. Rakov, "Perfect Difference Networks and Related Interconnection Structures for Parallel and Distributed Systems,"
*IEEE Trans. Parallel and Distributed Systems*, Vol. 16, No. 8, 2005, pp. 714-724.

**Packaging and Layout**

P1. Layout of High-Dimensional Mesh Networks (Not available for winter 2024)

[Weld09] A. Y. Weldezion, M. Grange, D. Pamunuwa, Z. Lu, A. Jantsch, R. Weerasekera, and H. Tenhunen, "Scalability of Network-on-Chip Communication Architecture for 3-D Meshes," *Proc. 3rd ACM/IEEE Int'l Symp. Networks-on-Chip*, pp. 114-123, 2009.

[Fors11] M. Forsell, V. Leppanen, and M. Penttonen, "Cost of Sparse Mesh Layouts Supporting Throughput Computing," *Proc. 14th Euromicro Conf. Digital System Design*, pp. 316-323, 2011.

P2. Layout of Multistage Interconnection Networks (Not available for winter 2024)

[Manu07] P. Manuel, K. Qureshi, A. William, and A. Muthumalai, "VLSI Layout of Benes Networks," *J. Discrete Mathematical Sciences and Cryptography*, Vol. 10, No. 4, pp. 461-472, 2007.

[Yeh00] C. H. Yeh, B. Parhami, E. A. Varvarigos, and H. Lee, "VLSI Layout and Packaging of Butterfly Networks," *Proc. 12th Annual ACM Symp. Parallel Algorithms and Architectures*, pp. 196-205, 2000.

P3. Design Considerations for Networks on Chip (Not available for winter 2024)

[Beni02] L. Benini and G. De Micheli, "Networks on Chip: A New Paradigm for Systems on Chip Design," *Proc. Conf. Design, Automation and Test in Europe*, pp. 418-419, 2002.

[Bolo04] E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, "Cost Considerations in Network on Chip," *Integration*, Vol. 38, No. 1, pp. 19-42, 2004.

P4. Energy for On-Chip vs. Off-Chip Network Links (Not available for winter 2024)

[Yayl98] G. I. Yayla, P. J. Marchand, and S. C. Esener, "Speed and Energy Analysis of Digital Interconnections: Comparison of On-Chip, Off-Chip, and Free-Space Technologies," *Applied Optics*, Vol. 37, No. 2, pp. 205-227, 1998.

[Sikd16] M. A. I. Sikder, "Emerging Technologies in On-Chip and Off-Chip Interconnection Network," Doctoral dissertation, Ohio University, 2016.

P5. Packaging Advantages of Hierarchical Networks (Assigned to: **Kai Han**)

[Ragh95] M. T. Raghunath and A. Ranade, "Designing Interconnection Networks for Multi-Level Packaging," *VLSI Design*, Vol. 2, No. 4, pp. 375-388, 1995.

[Unde12] K. D. Underwood and E. Borch, "Exploiting Communication and Packaging Locality for Cost-Effective Large Scale Networks," *Proc. 26th ACM Int'l Conf. Supercomputing*, pp. 291-300, 2012.

P6. Impact of Pruning on Network Packaging (Not available for winter 2024)

[Kwai98] D. M. Kwai and B. Parhami, "Pruned Three-Dimensional Toroidal Networks," *Information Processing Letters*, Vol. 68, No. 4, pp. 179-183, 1998.

[Rahm09] M. H. H. Rahman, X. Jiang, M. S. A. Masud, and S. Horiguchi, "Network Performance of Pruned Hierarchical Torus Network," *Proc. 6th IFIP Int'l Conf. Network and Parallel Computing*, pp. 9-15, 2009.

P7. Layout and Packaging Considerations for Dilated Networks (Assigned to: **TBD**)

[Parh16] B. Parhami, "Families of Communication Architectures for Data Centers and Parallel Processing Derived by Switching Network Dilation,"
*Scientia Iranica D*, Vol. 23, No. 6, 2016, pp. 2891-2897.

[Ragh93] M. T. Raghunath and A. Ranade, "Designing Interconnection Networks for Multi-Level Packaging," *Proc. ACM/IEEE Conf. Supercomputing*, 1993, pp. 772-781.

**Routing Algorithms**

R1. Oblivious Network Routing and Its Limitations (Assigned to: **TBD**)

[Iyen15] S. S. Iyengar and K. G. Boroojeni, *Oblivious Network Routing: Algorithms and Applications*, MIT Press, 2015.

[Towl02] B. Towles and W. J. Dally, "Worst-Case Traffic for Oblivious Routing Functions," *Proc. 14th Annual ACM Symp. Parallel Algorithms and Architectures*, pp. 1-8, 2002.

R2. Adaptive Routing in Networks (Assigned to: **TBD**)

[Duat95] J. Duato, "A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks," *IEEE Trans. Parallel and Distributed Systems*, Vol. 6, No. 10, pp. 1055-1067, 1995.

[Pere17] D. Perepelkin and M. Ivanchikova, "Improved Adaptive Routing Algorithm in Distributed Data Centers," *Advances in Electrical and Electronic Engineering*, Vol. 15, No. 3, pp. 502-508, 2017.

R3. Table-Assisted Routing in Networks (Assigned to: **Wushu Wan**)

[Bose14] A. Bose, P. Ghosal, and S. P. Mohanty, "A Low Latency Scalable 3D NoC Using BFT Topology with Table Based Uniform Routing," *Proc. IEEE Computer Society Annual Symp. VLSI*, pp. 136-141, 2014.

[Wang09] L. Wang, H. Song, Y. Jiang, and L. Zhang, "A Routing-Table-Based Adaptive and Minimal Routing Scheme on Network-on-Chip Architectures," *Computers & Electrical Engineering*, Vol. 35, No. 6, pp. 846-855, 2009.

R4. Deadlock-Free Routing in Networks (Not available for winter 2024)

[Duat01] J. Duato and T. M. Pinkston, "A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources," *IEEE Trans. Parallel and Distributed Systems*, Vol. 12, No. 12, pp. 1219-1235, 2001.

[Duat95] J. Duato, "A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks," *IEEE Trans. Parallel and Distributed Systems*, Vol. 6, No. 10, pp. 1055-1067, 1995.

R5. Broadcasting and Multicasting in Networks (Not available for winter 2024)

[Defa04] X. Defago, A. Schiper, and P. Urban, "Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey," *ACM Computing Surveys*, Vol. 36, No. 4, pp. 372-421, 2004.

[Haru06] H. A. Harutyunyan and B. Shao, "An Efficient Heuristic for Broadcasting in Networks," *J. Parallel and Distributed Computing*, Vol. 66, No. 1, pp. 68-76, 2006.

R6. Multi-Path Parallel Routing in Networks (Not available for winter 2024)

[Cido99] I. Cidon, R. Rom, and Y. Shavitt, "Analysis of Multi-Path Routing," *IEEE/ACM Trans. Networking*, Vol. 7, No. 6, pp. 885-896, 1999.

[Wang12] Y. Wang, W. S. Yang, and J. Wu, "Analysis of a Hypercube-Based Social Feature Multipath Routing in Delay Tolerant Networks," *IEEE Trans. Parallel and Distributed Systems*, Vol. 24, No. 9, pp. 1706-1716, 2012.

R7. Performance Evaluation of Hot-Potato Routing (Assigned to: **TBD**)

[Acam92] A. S. Acampora and S. I. A. Shah, "Multihop Lightwave Networks: A Comparison of Store-and-Forward and Hot-Potato Routing," *IEEE Trans. Communications*, Vol. 40, No. 6, 1992, pp. 1082-1090.

[Lu06] Z. Lu, M. Zhong, and A. Jantsch, "Evaluation of On-Chip Networks Using Deflection Routing," *Proc. ACM Great Lakes Symp. VLSI*, 2006, pp. 296-301.

**Theory and Foundations**

T1. The Degree-Diameter Problem in Networks (Assigned to: **TBD**)

[Mill12] M. Miller and J. Siran, "Moore Graphs and Beyond: A Survey of the Degree/Diameter Problem," *Electronic J. Combinatorics*, 2012.

[Stel20] P. Steller, *A Survey of the Degree/Diameter Problem for Undirected Graphs*, MS thesis, University of Delaware, 2020.

T2. Cayley Networks: Properties and Applications (Assigned to: **TBD**)

[Gane17] A. Ganesan, "Cayley Graphs and Symmetric Interconnection Networks," Preprint arXiv:1703.08109, 2017.

[Dema13] M. C. Heydemann, "Cayley Graphs and Interconnection Networks," In *Graph Symmetry: Algebraic Methods and Applications*, p. 167, 2013.

T3. Cartesian-Product Networks (Not available for winter 2024)

[Yous91] A. Youssef, "Cartesian Product Networks," *Proc. Int'l Conf. Parallel Processing*, pp. 684-685, 1991.

[Mora11] R. Moraveji, H. Sarbazi-Azad, and A. Y. Zomaya, "Performance Modeling of Cartesian Product Networks," *J. Parallel and Distributed Computing*, Vol. 71, No. 1, pp. 105-113, 2011.

T4. Connectivity of Networks (Not available for winter 2024)

[Li16] X. Li and Y. Mao, *Generalized Connectivity of Graphs*, Springer, 2016.

[Fran92] A. Frank, "Augmenting Graphs to Meet Edge-Connectivity Requirements," *SIAM J. Discrete Mathematics*, Vol. 5, No. 1, pp. 25-53, 1992.

T5. Hamiltonicity of Networks (Not available for winter 2024)

[Kewe11] C. D. Z. Kewen, "A Survey of the Advances of Hamiltonicity on Simple Graphs," *Mathematical Theory and Applications*, 2011.

[Xu09] J. M. Xu and M. Ma, "Survey on Path and Cycle Embedding in Some Networks," *Frontiers of Mathematics in China*, Vol. 4, No. 2, pp. 217-252, 2009.

T6. Network Mappings and Embeddings (Not available for winter 2024)

[Fisc13] A. Fischer, J. F. Botero, M. T. Beck, H. De Meer, and X. Hesselbach," "Virtual Network Embedding: A Survey," *IEEE Communications Surveys & Tutorials*, Vol. 15, No. 4, pp. 1888-1906, 2013.

[Rahm10] M. R. Rahman, I. Aib, and R. Boutaba, "Survivable Virtual Network Embedding," *Proc. Int'l Conf. Research in Networking*, pp. 40-52, 2010.

T7. Diagnosability of Interconnection Networks (Assigned to: **TBD**)

[Parh16] B. Parhami, N. Wu, and S. Tao, "Taxonomy and Overview of Distributed Malfunction Diagnosis in Networks of Intelligent Nodes,"
*J. Computer Science and Engineering*, Vol. 13, No. 2, 2016, pp. 23-31.

[Hsie08] S. Y. Hsieh and T. Y. Chuang, "The Strong Diagnosability of Regular Networks and Product Networks Under the PMC Model," *IEEE Trans. Parallel and Distributed Systems*, Vol. 20, No. 3, 2008, pp. 367-378.

Posters prepared for conferences must be colorful and eye-catching, as they are typically competing with dozens of other posters for the attendees' attention. Here are some tips and examples. Such posters are often mounted on a colored cardboard base, even if the pages themselves are standard PowerPoint slides. You can also prepare a "plain" poster (loose sheets, to be taped or pinned to a wall) that conveys your message in a simple and direct way. Eight to 10 pages, each resembling a PowerPoint slide, would be an appropriate goal. You can organize the pages into 2 x 4 (2 columns, 4 rows), 2 x 5, or 3 x 3 array on the wall. The top two of these might contain the project title, your name, course name and number, and a very short (50-word) abstract. The final two can perhaps contain your conclusions and directions for further work (including work that does not appear in the poster, but will be included in your research report). The rest will contain brief description of ideas, with emphasis on diagrams, graphs, tables, and the like, rather than text which is very difficult to absorb for a visitor in a short time span.

HW1 grades: Range = [B, A], Mean = 3.57, Median = A–

HW2 grades: Range = [B–, A], Mean = 3.33, Median = B+

HW3 grades: Range = [C+, A], Mean = 3.43, Median = B+/A–

HW4 grades: Range = [B–, A], Mean = 3.33, Median = B+

HW5 grades: Range = [B–, A+], Mean = 3.53, Median = A–

Overall homework grades (percent): Range = [65, 97], Mean = 85, Median = 88

Research paper grades: Range = [B–, A+], Mean = 3.40, Median = B+

Course letter grades: Range = [B, A+], Mean = 3.65, Median = A–

** Required text:** B. Parhami,

The following journals contain a wealth of information on new developments in parallel processing:

The following are the main conferences of the field: Int'l Symp. Computer Architecture (ISCA, since 1973), Int'l Conf. Parallel Processing (ICPP, since 1972), Int'l Parallel & Distributed Processing Symp. (IPDPS, formed in 1998 by merging IPPS/SPDP, which were held since 1987/1989), and ACM Symp. Parallel Algorithms and Architectures (SPAA, since 1988).

UCSB library's electronic journals, collections, and other resources

** Motivation:** The ultimate efficiency in parallel systems is to achieve a computation speedup factor of

*Catalog entry:* 254B. Advanced Computer Architecture: Parallel Processing(4) PARHAMI.*Prerequisites: ECE 254A. Lecture, 4 hours*. The nature of concurrent computations. Idealized models of parallel systems. Practical realization of concurrency. Interconnection networks. Building-block parallel algorithms. Algorithm design, optimality, and efficiency. Mapping and scheduling of computations. Example multiprocessors and multicomputers.

** History:** The graduate course ECE 254B was created by Dr. Parhami, shortly after he joined UCSB in 1988. It was first taught in spring 1989 as ECE 594L, Special Topics in Computer Architecture: Parallel and Distributed Computations. A year later, it was converted to ECE 251, a regular graduate course. In 1991, Dr. Parhami led an effort to restructure and update UCSB's graduate course offerings in the area of computer architecture. The result was the creation of the three-course sequence ECE 254A/B/C to replace ECE 250 (Adv. Computer Architecture) and ECE 251. The three new courses were designed to cover high-performance uniprocessing, parallel computing, and distributed computer systems, respectively. In 1999, based on a decade of experience in teaching ECE 254B, Dr. Parhami published the textbook

Offering of ECE 254B in winter 2023 (Link)

Offering of ECE 254B in winter 2022 (Link)

Offering of ECE 254B in winter 2021 (Link)

Offering of ECE 254B in winter 2020 (Link)

Offering of ECE 254B in winter 2019 (Link)

Offering of ECE 254B in winter 2018 (Link)

Offering of ECE 254B in winter 2017 (Link)

Offering of ECE 254B in winter 2016 (PDF file)

Offering of ECE 254B in winter 2014 (PDF file)

Offering of ECE 254B in winter 2013 (PDF file

Offering of ECE 254B in fall 2010 (PDF file)

Offering of ECE 254B in fall 2008 (PDF file)

Offerings of ECE 254B from 2000 to 2006 (PDF file)