Menu:
Behrooz Parhami's ECE 254B Course Page for Winter 2020
Adv. Computer Architecture: Parallel Processing
Page last updated on 2020 March 16
Enrollment code: 13508
Prerequisite: ECE 254A (can be waived, but ECE 154B is required)
Class meetings: MW 10:00-11:30, Phelps 1431
Instructor: Professor Behrooz Parhami
Open office hours: M 12:00-2:00, W 1:00-2:00, HFH 5155
Course announcements: Listed in reverse chronological order
Course calendar: Schedule of lectures, homework, exams, research
Homework assignments: Eight assignments, worth a total of 30%
Exams: Closed-book midterm, 30%; Closed-book final, 40%
Research paper: No research paper for winter 2020
Research paper guidlines: Brief guide to format and contents (N/A)
Poster presentation tips: Brief guide to format and structure (N/A)
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
Course Announcements
2020/03/16: The winter 2020 offering of ECE 254B is officially over and grades have been reported to the Registrar. I hope that the coronavirus health emergency ends soon, so that we can return to normal university activities. Meanwhile, UCSB faculty and staff will do their best to provide continuity in your educational pursuits via on-line classes (including my spring 2020 grad course on computer arithmetic), office hours, and as many of the other academic services as possible under the current conditions. Stay well, and hope to see you in person soon.
2020/03/15: I have informed each student via e-mail what his/her grade would be based on already-completed work, if s/he chooses not to take the optional final exam on 3/16. I realize that the situation is stressful for everyone and hope that this information will help you decide on the best course of action.
2020/03/14: Important announcement about our 3/16 final exam: I have received several inquiries about the wisdom of holding an in-person final exam amid fears and threat of the coronavirus epidemic. At this point, I cannot switch to a take-home final, given that the course design, my instruction, and your preparations were all based on the anticipation of a closed-book final exam.
Note that campus policies do allow holding an in-person final exam, if needed. Following one of the alternate recommendations for final exams from the campus administration, I have decided to make the in-person final exam optional. If you don't take the exam, your grade will be determined based on course assessments so far (homework assignements and midterm exam).
Everyone will be assigned a grade based on the alrealy-completed work. Taking the final exam can only raise your grade, not lower it. I hope this method alleviates your concerns about appearing in our smallish classroom with a number of others to take the final exam. The decision whether to take the final exam is now yours.
2020/03/10: Coronavirus update: Due to campuswide instructions not to hold in-person classes to the extent possible, I am cancelling the last lecture of the course on W 3/11. Powerpoint slides for the lecture are available on-line, as usual. I will be available to answer questions about the lecture slides during my normal office hour on W 3/11, 1:00-2:00 PM, and extra office hours on R 3/12, 1:00-3:00 PM. I will also appear in class on W 3/11, 10:00 AM, with solutions to HW8. You are not required to attend and can pick up the solutions during my office hours instead. Our final exam will be held as scheduled on M 3/16, 8:30-11:00 AM (in our regular classroom), as it is not possible for me to make alternate arrangements for the exam within the next few days.
2020/03/09: As announced in class today, I have added a couple of extra office hours on Thursday, March 12, 1:00-3:00 PM, ahead of our March 16 final exam.
2020/03/07: [News of possible interest] US NOAA signs contract with Cray Computing to triple its weather and climate supercomputing capacity and improve its forecast accuracy by closing the capabilities gap with its European counterparts.
2020/02/29: HW8 has been posted to the homework area below. I have also updated the study guide for the final exam. Here are links to my review of Rising on GoodReads and my Blog & Books page (the latter has a few charts/maps, which I don't know how to post on GoodReads. By Sunday 2020/03/01, I will post a summary of all of our micro-projects on my Blog & Books page. [Link]
2020/02/19: I have added selected lists of references after statements of uProjects B and C.
2020/02/16: HW6 has been posted to the homework area below. I have also posted HW7 (uProject D) ahead of schedule, in order to give you more flexibility in time management during a busy time of the quarter.
2020/02/11: UCSB faculty panel on climate change: Assembled at Goleta Valley Public Library on 2/9, the panel discussed Elizabeth Rush's Rising: Dispatches from the New American Shore. Many perspectives on the sea-level-rise problem, and climate change more generally, were presented, ranging from engineering/modeling aspects to policy issues. Rush's writing, and her putting a human face on the problem through telling compelling stories, were praised, but there were also criticisms of her inattention to the science behind sea-level rise and portraying all change as bad, whereas humans can in fact deal with and control some aspects of environmental changes.
2020/02/02: HW5 (uProject C) has been posted to the homework area below. Also, grade stats for HW3 have been compiled and posted.
2020/01/25: HW4 has been posted to the homework area below. Grade stats for HW2 have been posted.
2020/01/19: I have included a number of references for uProject A, following HW1's statement. Some of these may be useful for uProjects B-D as well. Grade stats for HW1 have been posted.
2020/01/17: HW3 (uProject B) has been posted to the homework area below. I will be returning my extra copies of the "UCSB Reads" book, Rising, to the library soon. If you have not received your free copy, let me know ASAP. Please look at the Web page for the student-organized group Numerical Scouts to see if you are interested in their aims and activities in the area of scientific computing. The contact e-mail address for the group is numerical.scouts.ucsb@gmail.com. Also, on Tuesday, January 14, there was a talk in Campbell Hall by atmospheric scientist Dr. Katharine Hayhoe. I learned about the talk too late to mention it in class beforehand, but this Facebook post of mine provides some information, as well as a link to Dr. Hayhoe's 17-minute TED talk on the topic.
2020/01/12: HW2 has been posted to the homework area below. If you have not received a free copy of the "UCSB Reads" book Rising, please see me.
2020/01/06: Please make sure to read the previous two course announcements, as they contain important information. HW1 (uProject A) has been posted to the homework area below. As of today, course enrollment stands at 22.
2019/11/17: Odd-numbered homework assignments: April 22, 2020, marks the 50th anniversary of Earth Day, kicked off a year after the Santa Barbara oil spill of winter 1969, which remains the largest spill off the coast of California (it is now the all-time third largest, including the subsequent Exxon Valdez and Deepwater Horizon incidents).
Winter is also the quarter during which our campus engages in "UCSB Reads," a program that began in 2007 and has chosen the book Rising: Dispatches from the New American Shore, by acclaimed author Elizabeth Rush, for campus perusal and discussion during 2020. The author will give a talk in UCSB's Campbell Hall on Monday, May 4, 2020, beginning at 7:30 PM.
Accordingly, I have decided to use four micro-projects as part of homework assignments for ECE 254B during winter 2020. The course's students will get free copies of Rising from UCSB Library. The micro-projects will explore the role of high-performance computing in modeling various aspects of climate change.
uProject A: From Weather Forecasting to Climate Modeling
uProject B: Ocean-Temperature Modeling: Monster Storms
uProject C: Modeling of Sea-Level Rise: Disappearing Lands
uProject D: Extreme-Weather Projections from Climate Data
For each micro-project, you will study the types of computer models involved, computational requirements of the models, how the computations are performed on top-of-the-line supercomputers, and data sets that allow drawing various conclusions from the modeling results.
2019/10/17: Welcome to the ECE 254B web page for winter 2020. Student sign-up for the course has not begun yet. I will be updating the lecture slides for 2020. Please wait for a 2020 date to appear alongside the files before downloading them. Looking forward to our first class session on Monday 2020/01/06.
Course Calendar
Course lectures and homework assignments have been scheduled as follows. 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 [Homework posted/due] {Special notes}
M 01/06 (1) Introduction to parallel processing
W 01/08 (2) A taste of parallel algorithms [HW1 posted; uProject A]
M 01/13 (3-4) Complexity and parallel computation models
W 01/15 (5) The PRAM shared-memory model and basic algorithms [HW1 due] [HW2 posted; chs. 1-4]
M 01/20 No lecture: Martin Luther King Holiday
W 01/22 (6A) More shared-memory algorithms [HW2 due] [HW3 posted, uProject B]
M 01/27 (6B-6C) Shared memory implementations and abstractions
W 01/29 (7) Sorting and selection networks [HW3 due] [HW4 posted; chs. 5-7]
M 02/03 (8A) Search acceleration circuits
W 02/05 (8B-8C) Other circuit-level examples [HW4 due] [HW5 posted; uProject C]
M 02/10 (1-7) Closed-book midterm exam {10:00-11:45 AM}
W 02/12 (9) Sorting on a 2D mesh or torus architectures [HW5 due]
M 02/17 No lecture: President's Day Holiday
W 02/19 (10) Routing on a 2D mesh or torus architectures [HW6 posted; chs. 8A-10]
M 02/24 (11-12) Other mesh/torus concepts
W 02/26 (13) Hypercubes and their algorithms [HW6 due] [HW7 posted; uProject D]
M 03/02 (14) Sorting and routing on hypercubes
W 03/04 (15-16) Other interconnection architectures [HW7 due] [HW8 posted; chs. 11-16]
M 03/09 (17) Emulation and task scheduling {Instructor/course evaluation surveys}
W 03/11 (18-19) Input/output and reliability considerations [HW8 due] {Class cancelled; see announcements}
M 03/16 (8A-19) Closed-book final exam {In our regular classroom, 8:30-11:00 AM}
T 03/25 {Course grades due by midnight}
Homework Assignments
- Turn in solutions as a single PDF file attached to an e-mail sent by the due date/time.
- 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: Micro-Project A (due W 2020/01/15, 10:00 AM)
From Weather Forecasting to Climate Modeling
Numerical weather prediction has a long history. As noted at the beginning of Section 1.3 of our textbook, British meteorologist Lewis Fry Richardson formulated a vision for using a large number of "computers" (humans, with mechanical calculators) to speed up the required calculations. Now, fast processors can do a decent job of running weather models and many thousands of processors can be used to perform the calculations required by more sophisticated models within hours, not weeks or months.
Your assignment is to prepare a single-spaced typed report (12-point font, 3 pages max, including figures and references) that discusses the computational requirements of modern weather prediction models, as well as models for climate forecasting, enumerating the differences between the two kinds of models in terms of the data they use, prediction time-frames, and the kinds of calculations involved. How does the availability of exascale computers help improve accuracy and execution speed for these models?
Here is a list of references for uProject A, collected mostly from your submitted project reports.
[Baue15] P. Bauer, A. Thorpe, and G. Brunet, "The quiet revolution of numerical weather prediction," Nature, Vol. 525, No. 7567, pp. 47-55, 2015.
[Boyd12] E. Boyd and E. L. Tompkins, Climate Change: A Beginner's Guide, Oneworld Publications, 2012.
[Char50] J. G. Charney, R. Fjortoft, and J. von Neumann, "Numerical integration of the barotropic vorticity equation," Tellus, Vol. 2, No. 4, pp. 237-254, 1950.
[Fuhr17] O. Fuhrer et al., "Near-global climate simulation at 1 km resolution: establishing a performance baseline on 4888 GPUs with COSMO 5.0," Geoscientific Model Development, Vol. 11, No. 4, pp. 1665-1681, 2018.
[Inno17] M. E. Innocenti et al., "Progress towards physics-based space weather forecasting with exascale computing," Advances in Engineering Software, Vol. 111, pp. 3-17, 2017.
[Lync08] P. Lynch, "The origins of computer weather prediction and climate modeling," J. Computational Physics, Vol. 227, No. 7, pp. 3431-3444, 2008.
[Mait13] S. Maity, S. Bonthu, K. Sasmal, and H. Warrior, "Role of parallel computing in numerical weather forecasting models," Int'l J. Computer Applications, Vol. 4, pp. 22-27, 2013.
[Marr15] S. Marras et al., "A review of element-based Galerkin methods for numerical weather prediction: Finite elements, spectral elements, and discontinuous Galerkin," Archives of Computational Methods in Engineering, Vol. 23, No. 4, pp. 673-722, 2016.
[Mull14] E. H. Muller and R. Scheichl, "Massively parallel solvers for elliptic partial differential equations in numerical weather and climate prediction," Quarterly J. Royal Meteorological Society, Vol. 140, No. 685, pp. 2608-2624, 2014.
[NRC12] National Research Council, A National Strategy for Advancing Climate Modeling, National Academies Press, 2012.
[Schu18] T. C. Schulthess et al., "Reflecting on the goal and baseline for Exascale Computing: A roadmap based on weather and climate simulations," Computing in Science & Engineering, Vol. 21, No. 1, pp. 30-41, 2018.
[Slin08] J. Slingo et al., "Developing the next-generation climate system models: challenges and achievements," Philosophical Trans. Royal Society—A: Mathematical, Physical and Engineering Sciences, Vol. 367, No. 1890, pp. 815-831, 2008.
Homework 2: Introduction, complexity, and models (chs. 1-4, due W 2020/01/22, 10:00 AM)
Do the following problems from the textbook: 1.10, 2.9, 3.7cd, 4.16 (defined below)
4.16 In-memory parallel computing
One of the approaches proposed for overcoming the memory wall is "in-memory" (or "near-memory") computation. Read the paper [Ali20] and answer the following questions.
a. What is "in-memory computing" (define precisely) and why is it useful?
b. Why opt for adding numbers bit-serially, the slowest addition scheme?
c. Can the methods discussed be extended to other arithmetic operations?
[Ali20] M. F. Ali, A. Jaiswal, and K. Roy, "In-Memory Low-Cost Bit-Serial Addition Using Commodity DRAM Technology," IEEE Trans. Circuits and Systems I, Vol. 67, No. 1, pp. 155-165, January 2020.
Homework 3: Micro-Project B (due W 2020/01/29, 10:00 AM)
Ocean-Temperature Modeling: Monster Storms
An aspect of climate and long-term weather modeling is predicting ocean temperatures, as briefly discussed on p. 7 of our textbook. One might think that the oceans all being connected to one another means that temperature should stabilize after a while to a common global ocean temperature. This is far from being the case, as this world-sea-temperatures map indicates.
So, a key question is: How do we go about predicting ocean temperatures in a decade? In 20 years? In 50 years? This is important, because ocean temperatures have a direct impact on the number and intensity of hurricanes and other storms, and they also affect weather phenomena more generally.
Your assignment is to prepare a single-spaced typed report (12-point font, 3 pages max, including figures and references) that discusses the computational requirements of ocean-temperatures forecasting models, the kinds of calculations involved, and trade-offs between model accuracy and computation time. [Link 1] [Link 2]
[Wand19] N. Wanders, M. T. H. van Vliet, Y. Wada, M. F. P. Bierkens, and L. P. H. van Beek, "High-Resolution Global Water Temperature Modeling," Water Resources Research, Vol. 55, pp. 2760-2778, April 2019.
Here is a list of references for uProject B, collected mostly from your submitted project reports.
[Abra13] J. P. Abraham et al., "A Review of Global Ocean Temperature Observations: Implications for Ocean Heat Content Estimates and Climate Change," Reviews of Geophysics, Vol. 51, No. 3, pp. 450-483, 2013.
[Harv19] C. Harvey, "Oceans Are Warming Faster than Predicted," Scientific American, E&E News Climate, January 2019.
[OCar19] A. G. O'Carroll et al., "Observational Needs of Sea Surface Temperature," Frontiers in Marine Science, Vol. 6, Article 420, 2019.
[vanB12] L. P. H. van Beek et al., "A Physically Based Model of Global Freshwater Surface Temperature," Water Resources Research, Vol. 48, No. 9, 2012.
[Ward06] B. Ward, "Near-Surface Ocean Temperature," J. Geophysical Research: Oceans, Vol. 111, No. C2, February 2006.
[Zann19] L. Zanna, S. Khatiwala, J. Gregory, J. Ison, and P. Heimbach, "Global Reconstruction of Historical Ocean Heat Storage and Transport," Proc. National Academy of Sciences, Vol. 116, No. 4, pp. 1126-1131, 2019.
Homework 4: Shared memory and sorting networks (chs. 5-7, due W 2020/02/05, 10:00 AM)
Do the following problems from the textbook: 5.12, 6.13, 7.9, 16.20ab (defined below)
16.20 Clos network
Consider a Clos network with rs inputs, rs outputs, and three columns (0-2) of switches. Columns 0 and 2 contain r switches, each of which is an s × s crossbar. Column 1 contains s switches that are r × r crossbars. Zero-origin top-to-bottom indexing is used to identify the switches in each column and their input/output lines. Switch terminals are identified by in(c, b, a) and out(c, b, a), with c being the column index, b the switch (block) index, and a the line index. Intercolumn connections are as follows:
for all x and y (0 ≤ x ≤ r – 1, 0 ≤ y ≤ s – 1),
out(0, x, y) is connected to in(1, y, x)
out(1, y, x) is connected to in(2, x, y)
a. Prove that the Clos network can realize any rs × rs permutation.
b. If the cost of an m × m crossbar switch is m^2 units, what are the optimal values of r and s for a given total number n = rs of inputs?
Homework 5: Micro-Project C (due W 2020/02/12, 10:00 AM)
Modeling of Sea-Level Rise: Disappearing Lands
Sea levels rise by three distinct mechanisms: (1) Thermal expansion; (2) Increase in water mass; (3) Depth changes due to movements in the Earth's crust. Predicting sea-level rise is important. Entire island nations will disappear with a rise of only a few feet. Other nations will lose low-lying coastal lands, which are usually densely-populated regions. New York and 16 other US cities will suffer significant displacements and property loss with just a 10-foot rise in sea level (some projections go well beyond 10 feet). Stories from some of these endangered US coastal regions are covered in the "UCSB Reads" book, Rising: Dispatches from the New American Shore. Cities like Venice (Italy) are particularly vulnerable to sea-level rise.
Your assignment is to prepare a single-spaced typed report (12-point font, 3 pages max, including figures and references) that discusses the computational requirements of sea-level rise models, the kinds of calculations involved, sources of uncertainty in the predictions, and probabilistic resolution of such uncertainties.
[Swee17] W. V. Sweet, R. Horton, R. E. Kopp, A. N. LeGrande, and A. Romanou, "Sea Level Rise," Climate Science Special Report: Fourth National Climate Assessment (Vol. I), D. J. Wuebbles, D. W. Fahey, K. A. Hibbard, D. J. Dokken, B. C. Stewart, and T. K. Maycock (eds.), US Global Change Research Program, Chapter 12, pp. 333-363, 2017.
Here is a list of references for uProject C, collected mostly from your submitted project reports.
[Doyl15] T. W. Doyle, B. Chivoiu, and N. M. Enwright, Sea-Level Rise Modeling Handbook—Resource Guide for Coastal Land Managers, Engineers, and Scientists, US Geological Survey Professional Paper 1815, 76 pp., 2015.
[Hay15] C. C. Hay et al., "Probabilistic Reanalysis of Twentieth-Century Sea-Level Rise," Nature, Vol. 517, No. 7535, pp. 481-484, 2015.
[Jevr12] S. Jevrejeva et al., "Sea Level Projections to AD2500 with a New Generation of Climate Change Scenarios," Global and Planetary Change, Vol. 80, pp. 14-20, January 2012.
[Leve13] A. Levermann, P. U. Clark, B. Marzeion, G. A. Milne, D. Pollard, V. Radic, and A. Robinson, "The Multimillennial Sea-Level Commitment of Global Warming," Proc. National Academy of Sciences, Vol. 110, No. 34, pp. 13745-13750, August 2013.
[Lind19] R. Lindsey, "Climate Change: Global Sea Level," Article posted on Climate.gov, NOAA, November 2019.
[Rahm07] S. Rahmstorf, "A Semi-Empirical Approach to Projecting Future Sea-Level Rise," Science, Vol 315, No. 5810, pp. 368-370, January 2007.
[Rahm12] S. Rahmstorf, "Modeling Sea Level Rise", Nature Education Knowledge, Vol. 3, No. 10, 2012.
[Viss15] H. Visser, S. Dangendorf, and A. C. Petersen, "A Review of Trend Models Applied to Sea Level Data with Reference to the 'Acceleration-Deceleration Debate'," J. Geophysical Research: Oceans, Vol. 120, pp. 3873-3895, June 2015.
Homework 6: Circuits and mesh/torus networks (chs. 8A-10, due W 2020/02/26, 10:00 AM)
Do the following problems from the textbook: 8.8, 9.7, 10.14abc, 10.19 (defined below)
10.19 Greedy routing on a 2D torus
Show that on an r-row, p-processor 2D torus, the greedy row-first routing algorithm solves a 1-1 routing problem in no more than r/2 + p/(2r) steps.
Homework 7: Micro-Project D (due W 2020/03/04, 10:00 AM)
Extreme-Weather Projections from Climate Data
The term "extreme weather" refers to intense heat/cold waves, widespread floods, prolonged droughts, severe winds, and the like. An analogy with performance records in sports and other domains might be helpful. Over time, sports records improve, because of enhanced techniques and better training, as well as random variations. However, there are factors at play that also lead to more frequent breaking of records. Examples include better equipment (e.g., soccer balls, running shoes, or baseball bats), which are sometimes viewed as giving modern atheletes an unfair edge. In the domain of music, record sales provide another example, where higher sales figures do not necessarily mean better music. In extreme-weather modeling, too, we look for underlying factors beyond random variations. Predicting droughts in California is one of the important areas of focus in the US.
Your assignment is to prepare a single-spaced typed report (12-point font, 3 pages max, including figures and references) that discusses the computational requirements of extreme-weather projection models, the kinds of calculations involved, and how the models tie in with those of the previous three micro-projects.
[Pete13] T. C. Peterson et al., "Monitoring and Understanding Changes in Heat Waves, Cold Waves, Floods and Droughts in the United States: State of Knowledge," Bull. American Meteorological Society, Vol. 94, pp. 821-834, June 2013.
Here is a list of references for uProject D, collected mostly from your submitted project reports.
[Hao18] Z. Hao, V. P. Singh, and Y. Xia, "Seasonal Drought Prediction: Advances, Challenges, and Future Prospects," Reviews of Geophysics, Vol. 56, No. 1, pp. 108-141, 2018.
[Lubc12] J. Lubchenco and T. R. Karl, "Predicting and Managing Extreme Weather Events," Physics Today, Vol. 65, No. 3, p. 31, 2012.
[Meeh00] G. A. Meehl, F. Zwiers, J. Evans, T. Knutson, L. Mearns, and P. Whetton, "Trends in Extreme Weather and Climate Events: Issues Related to Modeling Extremes in Projections of Future Climate Change," Bull. American Meteorological Society, Vol. 81, No. 3, pp. 427-436, 2000.
[Sill17] J. Sillmann et al., "Understanding, Modeling and Predicting Weather and Climate Extremes: Challenges and Opportunities," Weather and Climate Extremes, Vol. 18, pp. 65-74, 2017.
[Vavr15] S. J. Vavrus, M. Notaro, and D. J. Lorenz, "Interpreting Climate Model Projections of Extreme Weather Events," Weather and Climate Extremes, Vol. 10, pp. 10-28, 2015.
[Zwie13] F. W. Zwiers, L. V. Alexander, G. C. Hegerl, T. R. Knutson, J. P. Kossin, P. Naveau, N. Nicholls, C. Schar, S. I. Seneviratne, and X. Zhang, "Climate Extremes: Challenges in Estimating and Understanding Recent Changes in the Frequency and Intensity of Extreme Climate and Weather Events," in Climate Science for Serving Society, Springer, 2013, pp. 339-389.
Homework 8: Hypercubic and other architectures (chs. 11-16, due W 2020/03/11, 10:00 AM)
Do the following problems from the textbook: 12.24 (defined below), 13.14, 15.3, 16.2
12.24 Twin torus topology
Read the paper [Andu15] about h-D twin torus topology and answer the following questions.
a. Describe the proposed topology in no more than two sentences.
b. What is the main advantage of twin torus over ordinary torus with the same number of nodes?
c. What is a primary disadvantage of twin torus compared with ordinary torus? Explain.
d. Propose a generalization to triplet torus topology and cite its advantages and disadvantages.
[Andu15] Andujar-Munoz, F. J., J. A. Villar-Ortiz, J. L. Sanchez, F. J. Alfaro, and J. Duato, "N-Dimensional Twin Torus Topology," IEEE Trans. Computers, Vol. 64, No. 10, pp. 2847-2861, October 2015.
Sample Exams and Study Guides
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 i + s corrected to j + s), 7.6a, and 8.4ac; note that problem statements might change a bit for a closed-book exam.
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
Research Paper and Presentation
[Not for winter 2020] Our research focus this quarter will be on the topical area of big data, as defined in class and the reading/research assignments for the first three course homeworks. We will study the intersection of big data with high-performance computing, that is, how the meteoric spread of big-data applications affects the field of parallel/distributed computing and how research in our field can help solve the challenges brought about by big data.
The "4 Vs" of big data are nicely illustrated in the following IBM infographic. The fourth "V," equated in the image with "veracity," having to do with correctness and accuracy of data, is sometimes replaced by "value" (see the ssecond homework assignment), the data's importance or worth to an enterprise or application. Alternatively, one might view the big-data domain as being defined by "5 Vs."
Here is a list of research paper titles. I am posting the list, even though some of the info is incomplete, in order to give you a head start on choosing a topic. In topic selection, you can either propose a topic of your choosing, which I will review and help you refine into something that would be manageable and acceptable for a term paper, or you can give me your first to third choices among the topics that follow. I will then assign a topic to you by February 12, based on your preferences and those of your classmates. Sample references follow the titles to help define the topics and serve as starting pointa for your study.
1. Hybrid Disk Drives for Big-Data Storage Needs (Assigned to: )
[Wu09] X. Wu and A. L. Narasimha Reddy, "Managing Storage Space in a Flash and Disk Hybrid Storage System," Proc. IEEE Int'l Symp. Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2009, pp. 1-4.
Search terms: Flash disk cache
2. GPU-Based Parallel Architectures for Big Data (Assigned to: )
[Liu13] Z. Liu, B. Jiang, and J. Heer, "imMens: Real-Time Visual Querying of Big Data," Computer Graphics Forum, Vol. 32, No. 3, 2013, pp. 421-430.
Search terms: GPU-based supercomputing
3. Network Coding for Fast Exchange of Big Data (Assigned to: )
[Dima10] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, "Network Coding for Distributed Storage Systems," IEEE Trans. Information Theory, Vol. 56, No. 9, 2010, pp. 4539-4551.
Search terms:
4. Big-Data Allocation and Load-Balancing Methods (Assigned to: )
[Wang14] K. Wang, X. Zhou, T. Li, D. Zhao, M. Lang, and I. Raicu, "Optimizing Load Balancing and Data-Locality with Data-Aware Scheduling," Proc. IEEE Int'l Conf. Big Data, 2014, pp. 119-128.
Search terms:
5. Low-Redundancy Methods for Big-Data Protection (Assigned to: )
[Amja12] T. Amjad, M. Sher, and A. Daud, "A Survey of Dynamic Replication Strategies for Improving Data Availability in Data Grids," Future Generation Computer Systems, Vol. 28, No. 2, 2012, pp. 337-349.
Search terms:
6. RAID in the Era of Cloud-Based Big-Data Storage (Assigned to: )
[Gu14] M. Gu, X. Li, and Y. Cao, "Optical Storage Arrays: A Perspective for Future Big Data Storage," Light: Science & Applications, Vol. 3, No. 5, 2014.
Search terms:
7. Structural Representations for Big-Data Storage (Assigned to: )
[Sand14] A. Sandryhaila and J. M. F. Moura, "Big Data Analysis with Signal Processing on Graphs: Representation and Processing of Massive Data Sets with Irregular Structure," IEEE Signal Processing, Vol. 31, No. 5, 2014, pp. 80-90.
Search terms:
8. Meeting Reliability Requirements of Big Data (Assigned to: )
[Sath13] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur, "XORing Elephants: Novel Erasure Codes for Big Data," Proc. Symp. VLDB, Vol. 6, No. 5, 2013, pp. 325-336.
Search terms: Reliable distributed systems; Data integrity
9. Search and Query Optimizations for Big Data (Assigned to: )
[Du92] W. Du, R. Krishnamurthy, and M.-C. Shan. "Query Optimization in a Heterogeneous DBMS," Proc. Symp. VLDB, 1992, Vol. 92, pp. 277-291.
Search terms:
10. The MapReduce Paradigm for Big-Data Parallelism (Assigned to: )
[Dean10] J. Dean and S. Ghemawat, "MapReduce: A Flexible Data Processing Tool," Communications of the ACM, Vol. 53, No. 1, 2010, pp. 72-77.
Search terms: Data-parallel computing; Divide-and-conquer paradigm
11. Hadoop's Distributed File System for Big Data (Assigned to: )
[Shva10] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, "The Hadoop Distributed File System," Proc. 26th IEEE Symp. Mass Storage Systems and Technologies, 2010, pp. 1-10.
Search terms: Hadoop; Distributed file systems; Distributed databases
12. Big-Data Longevity and Compatibility Challenges (Assigned to: )
[Garf04] T. Garfinkel, B. Pfaff, J. Chow, and M. Rosenblum, "Data Lifetime Is a Systems Problem," Proc. 11th ACM SIGOPS European Workshop, 2004, p. 10.
Search terms: Data preservation; Long-term data archiving
13. Advances in Intelligent Systems with Big Data (Assigned to: )
[OLea13] D. E. O'Leary, "Artificial Intelligence and Big Data," IEEE Intelligent Systems, Vol. 28, No. 2, 2013, pp. 96-99.
Search terms: Data-driven AI; Large training data-sets
14. FPGA-Based Accelerators for Big-Data Computing (Assigned to: )
[Wang15] C. Wang, X. Li, and X. Zhou, "SODA: Software Defined FPGA Based Accelerators for Big Data," Proc. Design Automation & Test Europe Conf., 2015, pp. 884-887.
Search terms: Hardware accelerators; Application-specific coprocessors
15. Big-Data Aspects of Distributed Sensor Networks (Assigned to: )
[Taka14] D. Takaishi, H. Nishiyama, N. Kato, and R. Miura, "Toward Energy Efficient Big Data Gathering in Densely Distributed Sensor Networks," IEEE Trans. Emerging Topics in Computing, Vol. 2, No. 3, pp. 388-397, 2014.
Search terms: Ad-hoc networks; Data storage in sensor networks
16. Big-Data Challenges of Maps and Auto-Navigation (Assigned to: )
[Shek12] S. Shekhar, V. Gunturi, M. R. Evans, and K. Yang, "Spatial Big-Data Challenges Intersecting Mobility and Cloud Computing." Proc. 11th ACM Int'l Workshop Data Engineering for Wireless and Mobile Access, 2012, pp. 1-6.
Search terms: Geographic information systems; GPS navigation
17. Shared-Memory Models for Big-Data Applications (Assigned to: )
[Bell18] C. G. Bell and I. Nassi, "Revisiting Scalable Coherent Shared Memory," IEEE Computer, Vol. 51, No. 1, pp. 40-49, January 2018.
Search terms: Memory consistency; Distributed shared memory; Directory-based coherence
18. Edge Computing for Big Data (Assigned to: )
[Shar17] S. K. Sharma and X. Wang, "Live Data Analytics With Collaborative Edge and Cloud Processing in Wireless IoT Networks," IEEE Access, Vol. 5, pp. 4621-4635, 2017.
Poster Presentation Tips
[Not for winter 2020] 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
All grades listed below are in [0.0, 4.3] (F to A+), unless otherwise noted
HW1 grades: Range = [B+, A+], Mean = 3.8, Median = A–
HW2 grades: Range = [B, A+], Mean = 3.7, Median = A–
HW3 grades: Range = [B+, A+], Mean = 3.8, Median = A–
HW4 grades: Range = [B+, A+], Mean = 3.7, Median = A–
HW5 grades: Range = [B+, A+], Mean = 3.8, Median = A–
HW6 grades: Range = [C–, A+], Mean = 3.6, Median = A–
HW7 grades: Range = [B, A], Mean = 3.7, Median = A–
HW8 grades: Range = [D+, A+], Mean = 3.5, Median = A–
Overall homework grades (percent): Range = [00, 00], Mean = 00, Median = 00
Midterm exam grades (percent): Range = [53, 97], Mean = 75, Median = 73
Optional final exam grades (percent): Range = [34, 79], Mean = 58, Median = 59
Course letter grades: Range = [B, A+], Mean = 3.6, Median = A–
References
Required text: B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Plenum Press, 1999. Make sure that you visit the textbook's web page which contains an errata. Lecture slides are also available there.
Required supplemental reading: E. Rush, Rising: Dispatches from the New American Shores, Milkweed Editions, 2018. [ECE 254B students can obtain free copies of this book from the UCSB Library, as part of the 2020 "UCSB Reads" program.]
Optional recommended book: T. Rauber and G. Runger, Parallel Programming for Multicore and Cluster Systems, 2nd ed., Springer, 2013. Because ECE 254B's focus is on architecture and its interplay with algorithms, this book constitutes helpful supplementary reading.
On-line: N. Matloff, Programming Parallel Machines: GPU, Multicore, Clusters, & More. [Link]
Research resources:
The follolwing journals contain a wealth of information on new developments in parallel processing: IEEE Trans. Parallel and Distributed Systems, IEEE Trans. Computers, J. Parallel & Distributed Computing, Parallel Computing, Parallel Processing Letters, ACM Trans. Parallel Computing. Also, see IEEE Computer and IEEE Concurrency (the latter ceased publication in late 2000) for broad introductory articles.
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
Miscellaneous Information
Motivation: The ultimate efficiency in parallel systems is to achieve a computation speedup factor of p with p processors. Although often this ideal cannot be achieved, some speedup is generally possible by using multiple processors in a concurrent (parallel or distributed) system. The actual speed gain depends on the system's architecture and the algorithm run on it. This course focuses on the interplay of architectural and algorithmic speedup techniques. More specifically, the problem of algorithm design for "general-purpose" parallel systems and its "converse," the incorporation of architectural features to help improve algorithm efficiency and, in the extreme, the design of algorithm-based special-purpose parallel architectures, are dealt with. The foregoing notions will be covered in sufficient detail to allow extensions and applications in a variety of contexts, from network processors, through desktop computers, game boxes, Web server farms, multiterabyte storage systems, and mainframes, to high-end supercomputers.
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 Introduction to Parallel Processing: Algorithms and Architectures (Website).
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)