Behrooz Parhami's website banner

Menu:

Behrooz Parhami's ECE 257A Course Page for Fall 2013

Collapsed bridge

Fault-Tolerant Computing

Page last updated on 2013 December 16

Enrollment code: 13219
Prerequisite: ECE 154 (or equivalent)
Class meetings: MW 10:00-11:30, Phelps 1431
Instructor: Professor Behrooz Parhami
Open office hours: MW 3:30-5:00; HFH 5155
Course announcements: Listed in reverse chronological order
Course calendar: Lecture, homework, and exam schedules
Homework assignments: Four assignments, worth a total of 20%
Exams: Open-book midterm; worth 30% (no final)
Research paper: See course calendar for schedule; worth 50%
Research paper guidlines: Brief guide to format and contents
Poster presentation tips: Brief guide to format and structure
Grades: Statistics for homework and exam grades
References: Textbook and other sources (Textbook's web page)
Lecture slides: Via the textbook's Web page
Miscellaneous information: Motivation, catalog entry, history

Course Announcements

Megaphone

2013/12/16: The fall 2013 offering of ECE 257A is officially over. Grades have been reported to the Registrar's office and they have been e-mailed to students, along with feedback on the research paper. My winter 2014 office hours will be MW 3:30-5:00. Happy holidays!
2013/12/05: Feedback on your research poster presentation was e-mailed to you earlier today. The final paper will be due by the end of the day on R 12/12. There were a couple of errors in my solutions to Homework 4. I will prepare a revised solutions sheet that you can pick up from my office next week. I will continue to hold my office hours during the finals week.
2013/11/23: Homework 4 has been posted and the textbook and lecture slides have been updated for Parts V and VI. Corresponding updates for Part VII will be posted no later than Friday 11/29. Please note the new section on this page entitled "Poster Presentation Tips."
2013/11/04: Homework 3 has been posted to the homework area below. Our open-book/notes midterm exam will be held on W 11/06. There will be no lecture on M 11/11 (Veterans Day holiday).
2013/10/29: Research topic assignments have now been finalized. The next milestone for your term paper is submission of a research plan and preliminiary references by W 11/13.
2013/10/25: Part IV of the textbook and its associated lecture slides have been updated for fall 2013.
2013/10/21: Today's updates to the course Web page include the listing of 9 research topics, along with references that provide context and starting points. Research topic selection was due by W 10/23, but the deadline has been extended to M 10/28. Also, lecture slides are now up to date until the end of Part III; corresponding updates to the textbook will appear by W 10/23.
2013/10/19: Homework 2 has been posted to the homework area below. Also, Part II of the textbook and its associated lecture slides have been updated for fall 2013. Part III will be updated before W 10/23.
2013/10/05: Homework 1 has been posted to the homework area below. Also, Part I of the textbook and its associated lecture slides are now up to date for fall 2013.
2013/09/25: Please note that there will be no lecture on M 9/30 due to the instructor's travel plans. You should go over the slides preceding those of Chapter 1 in the presentation file for Part I of the textbook (accessible via our textbook's Web page) and bring any questions to class or to office hours.
2013/06/10: Welcome to the ECE 257A web page for fall 2013. Thus far, 15 students have signed up for the class and I look forward to meeting you all in fall. The following information is provided for planning purposes only. Details will be finalized in late September and updated regularly thereafter. I will be updating and improving the on-line course textbook and lecture slides over the summer, so the fall 2013 contents will be different from the current version. Please pay attention to the associated posting date when downloading material for the course.

Course Calendar

Calendar

Course lectures, homework assignments, and exams, have been scheduled as follows. This schedule will be strictly observed. In particular, no extension is possible for homework due dates. Please begin work on your assignments early. Each lecture corresponds to topics in 1-2 chapters of the instructor's forthcoming textbook on dependable computing. Chapter numbers are provided in parentheses, after day & date.

Day & Date (book chapters) Lecture topic [Homework posted/due] {Special notes}
M 09/30 (0) Class cancelled due to instructor's travel plans {Lecture included in the slides for chs. 1-4}
W 10/02 (1) Background and motivation

M 10/07 (2) Dependability attributes [HW1 posted, chs. 1-4]
W 10/09 (3) Combinational modeling

M 10/14 (4) State-space modeling
W 10/16 (5, 7) Defect avoidance; Shielding and hardening [HW1 due]

M 10/21 (6, 8) Defect circumvention; Yield enhancement [HW2 posted, chs. 5-12]
W 10/23 (9, 11) Fault testing; Design for testability {Research topic selection deadline (extended)}

M 10/28 (10, 12) Fault masking; Replication with voting {Extended topic selection deadline}
W 10/30 (13, 15) Error detection; Self-checking modules [HW2 due]

M 11/04 (14, 16) Error correction; Redundant disk arrays
W 11/06 (1-16) Midterm exam, open-book/notes, 10:00-11:45 [HW3 posted, chs. 13-20]

M 11/11 No lecture: Veterans' Day holiday
W 11/13 (17, 19) Malfunction diagnosis; Standby redundancy {Research plan and preliminary references due}

M 11/18 (18, 20) Malfunction tolerance; Robust parallel processing
W 11/20 (21-22) Degradation allowance; Resilient algorithms [HW3 due]

M 11/25 (23-24) Degradation management; Software redundancy [HW4 posted, chs. 21-28]
W 11/27 (25, 27) Failure confinement; Agreement and adjudication {Abstract and final references due}

M 12/02 (26, 28) Failure recovery; Fail-safe systems {Instructor and course evaluations?}
W 12/04 Research poster presentations [HW4 due] {PDF of posters due by midnight}

R 12/12 {PDF of final research paper due by midnight}
W 12/18 {Course grades due by midnight}

Homework Assignments

Homework image

-Turn in solutions in class before the lecture begins.
-Because solutions will be handed out on the due date, no extension can be granted.
-Use a cover page that includes your name, course name, and assignment number.
-Staple the sheets and write your name on top of each sheet in case they are separated.
-Although some cooperation is permitted, direct copying will have severe consequences.

Homework 1: Dependability and its modeling (ch. 1-4, due W 2013/10/16, 10:00 AM)
Do the following problems from the textbook or defined below: 1.7, 1.19, 2.14, 3.15, 4.1
1.19 Reliability and robustness vs. efficiency
Read the viewpoint [Ackl13] explaining why undue emphasis on efficiency undermines reliability and robustness. Write a 200-word abstract for the article, summarizing its main points and argument.
[Ackl13] D.H. Ackley, "Beyond Efficiency," Communications of the ACM, Vol. 56, No. 10, pp. 38-40, Oct. 2013.

Homework 2: Defects and faults (ch. 5-12, due W 2013/10/30, 10:00 AM)
Do the following problems from the textbook: 5.1, 8.4, 9.3, 11.1, 12.2

Homework 3: Errors and malfunctions (ch. 13-20, due W 2013/11/20, 10:00 AM)
Do the following problems from the textbook: 13.6, 13.8, 14.6abc, 16.3abd, 17.4

Homework 4: Degradations and failures (ch. 21-28, due W 2013/12/04, 10:00 AM)
Do the following problems from the textbook: 21.3, 23.1, 24.8, 27.3, A.1

Sample Exams and Study Guide

Answer sheet

The following sample exam problems 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 and class handouts that are not explicitly excluded in the study guide that follows each sample exam, even if the material was not covered in class lectures.

Sample Midterm Exam (105 minutes)
Problems 3.12, 4.4, 9.4, and 12.1 from the textbook.

Midterm Exam Study Guide
Nothing specific; just study Chapters 1-16 and review the problems in homework assignments 1-2.

Sample Final Exam (120 minutes)
There will be no final exam in the fall 2013 offering of ECE 257A. The following are from a previous offering.
Problems 13.5, 15.5, 17.1, and 21.2 from the textbook.

Final Exam Study Guide
Study Chapters 13-28. There will be one problem from each of the four parts. Pay special attention to the problems in homework assignments 3-4. Note that the coverage in the sample final exam above is more limited than that of the current quarter.

Research Paper and Presentation

Colored marbles

Each student will review a subfield of dependable computing or do original research on a selected and approved topic. A preliminary list of research topics is provided below (new topics, and new references for the current topics, may be added later). However, students should feel free to propose their own topics for approval. To propose a topic, send via e-mail a one-page narrative, including 2-3 key references, to the instructor.

A publishable report earns an "A" for the course, regardless of homework and midterm grades. See the course calendar for schedule and due dates and Research Paper Guidlines for formatting tips.

This year's suggested research topics for ECE 257A are built around the theme "Robustness of Interconnection networks." You can get started on each topic by taking a look at the following two common references, plus one topic-specific reference that is provided further down on this page. The two common references are:

[Parh10] Parhami, B., "Robustness Attributes of Interconnection Networks for Parallel Processing," Keynote Lecture at the First Int'l Supercomputing Conf., Guadalajara, Mexico, March 2010. {PPT and PDF slides are available from B. Parhami's Publications Web page; see publication [262].}

[Sall12] Salles, R. M. and D. A. Marion Jr., "Strategies and Metric for Resilience in Computer Networks," Computer J., Vol. 55, No. 6, pp. 728-739, June 2012.

1. Effects of Missing Nodes on Network Diameter and Average Distance (Assigned to: Changhao Huang)
[Kris87] Krishnamoorthy, M.S. and B. Krishnamurthy, "Fault Diameter of Interconnection Networks," Computers & Mathematics with Applications, Vol. 13, Nos. 5/6, pp. 577-582, 1987.

2. Effects of Missing Links on Network Diameter and Average Distance (Assigned to: Mingjia Han)
[Kris87] Krishnamoorthy, M.S. and B. Krishnamurthy, "Fault Diameter of Interconnection Networks," Computers & Mathematics with Applications, Vol. 13, Nos. 5/6, pp. 577-582, 1987.

3. Synthesis of Interconnection Networks with Maximal Fault Tolerance (Assigned to: Shrikant Kulkarni)
[Chen09] W. Chen, W. J. Xiao, and B. Parhami, "Swapped (OTIS) Networks Built of Connected Basis Networks are Maximally Fault Tolerant," IEEE Trans. Parallel and Distributed Systems, Vol. 20, pp. 361-366, March 2009.

4. Adaptive Schemes for Point-to-Point Communication in Networks (Assigned to: Eric Goodman)
[Ngai91] Ngai, J. Y. and C. L. Seitz, "A Framework for Adaptive Routing in Multicomputer Networks," Computer Architecture News, Vol. 19, No. 1, pp. 6-14, March 1991.

5. Adaptive Schemes for Collective Communication in Networks (Assigned to: Krishna Mosalakanti)
[Pand95] Panda, D. K., "Issues in Designing Efficient and Practical Algorithms for Collective Communication on Wormhole-Routed Systems," Proc. Int'l Conf. Parallel Processing Workshop on Challenges for Parallel Processing, 1995, pp. 8-15.

6. Deadlocks in Adaptive Routing and How to Avoid or Detect Them (Assigned to: Jeff Heckey)
[Dall93] Dally, W. J. and H. Aoki, "Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels," IEEE Trans. Parallel and Distributed Systems, Vol. 4, No. 4, pp. 466-475, April 1993.

7. Diagnosability of Regular Degree-d Interconnection Networks (Assigned to: Yueran Meng)
[Chan05] Chang, G.-Y., G. J. Chang, and G.-H. Chen, "Diagnosabilities of Regular Networks," IEEE Trans. Parallel and Distributed Systems, Vol. 16, No. 4, pp. 314-323, April 2005

8. Diagnosability of Hierarchical or Multilevel Interconnection Networks (Assigned to: TBD)
[Xu09] Xu, M., K. Thulasiraman, and X.-D. Hu, "Conditional Diagnosability of Matching Composition Networks Under the PMC Model," IEEE Trans. Circuits and Systems II, Vol. 56, No. 11, pp. 875-879, November 2009.

9. Synthesis of Interconnection Networks with Maximal Diagnosability (Assigned to: TBD)
[Chan05] Chang, G.-Y., G. J. Chang, and G.-H. Chen, "Diagnosabilities of Regular Networks," IEEE Trans. Parallel and Distributed Systems, Vol. 16, No. 4, pp. 314-323, April 2005

Topics outside the main theme for the quarter

10. Software Fault Monitoring (Proposed by and assigned to: Brian Neely)
[Delg04] Delgado, N., A. Q. Gates, and S. Roach, "A Taxonomy and Catalog of Runtime Software-Fault Monitoring Tools," IEEE Trans. Software Engineering, Vol. 30, No. 12, pp. 859-872, December 2004

Poster Presentation Tips

Poster format

Here are some guidelines for preparing your research poster. The idea of the poster is to present your research results and conclusions thus far, get oral feedback during the session from the instructor and your peers, and to provide the instructor with something to comment on before your final report is due. Please send a PDF copy of the poster via e-mail by midnight on the poster presentation day.

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 is an example of a conference poster. Such posters are often mounted on a colored cardboard base, even if the pages themselves are standard PowerPoint slides. In our case, you should aim for a "plain" poster (loose sheets, to be taped to the wall in our classroom) 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 very limited time span.

Grade Statistics

Chart

All grades listed are in percent, unless otherwise noted.
HW1 grades: Range = [67, 94], Mean = 80, Median = 80
HW2 grades: Range = [63, 89], Mean = 83, Median = 89
HW3 grades: Range = [63, 95], Mean = 81, Median = 85
HW4 grades: Range = [58, 96], Mean = 88, Median = 93
Midterm exam grades: Range = [37, 95], Mean = 72, Median = 81
Research paper grades: Range = [60, 90], Mean = 80, Median = 83
Course grades, A-F: Range = [3.0, 4.0], Mean = 3.7, Median = 3.8

References

Image of a reference book

Required text: B. Parhami, Dependable Computing: A Multilevel Approach, chapters will be posted as they are updated. Please visit the textbook's web page for general information. Lecture slides are also available there.
Some useful books (not required):
Koren/Krishna, Fault-Tolerant Systems, Morgan Kaufmann, 2007 (ISBN 0-12-088525-5)
Shooman, Reliability of Computer Systems and Networks, Wiley, 2002 (ISBN 0-471-29342-3)
Siewiorek/Swarz, Reliable Computer Systems, Digital Press, 1992 (ISBN 1-55558-075-0)
Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addison Wesley, 1989 (ISBN 0-201-07570-9)

Research resources:
Proc. IEEE/IFIP Int'l Conf. Dependable Systems and Networks (DSN), formerly known as Fault-Tolerant Computing Symp. (FTCS), annual, since 1971.
IEEE Trans. Dependable and Secure Computing, quarterly journal, published since 2004
IEEE Trans. Reliability, Quarterly journal, published since 1955
IEEE Trans. Computers, monthly journal, published since 1952
UCSB library's electronic journals, collections, and other resources

Miscellaneous Information

Motivation: Dependability concerns are integral parts of engineering design. Ideally, we would like our computer systems to be perfect, always yielding timely and correct results. However, just as bridges collapse and airplanes crash occasionally, so too computer hardware and software cannot be made totally immune to unpredictable behavior. Despite great strides in component reliability and programming methodology, the exponentially increasing complexity of integrated circuits and software systems makes the design of prefect computer systems nearly impossible. In this course, we study the causes of computer system failures (impairments to dependability), techniques for ensuring correct and timely computations despite such impairments, and tools for evaluating the quality of proposed or implemented solutions.

Catalog entry: 257A. Fault-Tolerant Computing. (4) PARHAMI. Prerequisites: ECE 154. Lecture, 3 hours. Basic concepts of dependable computing. Reliability of nonredundant and redundant systems. Dealing with circuit-level defects. Logic-level fault testing and tolerance. Error detection and correction. Diagnosis and reconfiguration for system-level malfunctions. Degradation management. Failure modeling and risk assessment.

History: Professor Parhami took over the teaching of ECE 257A in the fall quarter of 1998. Previously, the course had been taught primarily by Dr. John Kelly, who instituted the two-course sequence ECE 257A/B, the first covering general topics and the second (now discontinued) devoted to his research focus on software fault tolerance. Borrowing from his experience in teaching dependable computing at other universities and based on an extensive survey of the field that he published in 1994, Professor Parhami oriented the course toward an original multilevel view of impairments to computer system dependability and techniques for avoiding or tolerating them. The levels of this models, in increasing order of abstraction, are: defects, faults, errors, malfunctions, degradations, and failures. A textbook based on this multilevel model of dependable computing is in preparation.
Offering of ECE 257A in fall 2013 (PDF file)
Offering of ECE 257A in fall 2012 (PDF file)
Offering of ECE 257A in fall 2009 (PDF file)
Offering of ECE 257A in fall 2007 (PDF file)
Offerings of ECE 257A in 1998 and 2006 (PDF file)