📄 http:^^www.cs.hmc.edu^~keller^cs156.html
字号:
Date: Tue, 26 Nov 1996 18:40:55 GMT
Server: NCSA/1.5.1
Last-modified: Tue, 16 Jan 1996 21:09:57 GMT
Content-type: text/html
Content-length: 6043
<html><HEAD><TITLE>CS 156: Parallel and Real-Time Computation</TITLE></HEAD><BODY>URL http://www.cs.hmc.edu/~keller/cs156.html<H3><!WA0><a href = "http://www.hmc.edu/">Harvey Mudd College</a> Spring 1996</H3><H3><!WA1><A HREF="http://www.cs.hmc.edu/index.html">Computer Science</A> 156: Parallel and Real-Time Computation</H3><h3>Course Personnel:</h3><ul><li>Instructor: <!WA2><a href = "http://www.cs.hmc.edu/~keller"> Robert Keller </a>242 Olin (4-5 p.m. MTuWTh or by appt.), keller@muddcs, x 18483<br><br><li>Secretary: <!WA3><a href = "http://www.cs.hmc.edu/~nancy"> Nancy Mandala</a> 240 Olin (1-5 M-F) nancy@muddcs, x 18225<br><br><li>CS Intern (for account problems, etc.): <!WA4><a href = "http://www.cs.hmc.edu/~tom"> TBD</a>, 101 Beckman, TBD@muddcs, x 73485</ul><P> <DT><h3>Catalog Description</h3> <P> Characteristics andapplications of parallel and real-time systems. Specificationtechniques, architectures, languages, design, and implementation. 3credit hours. <br><br>Prerequisites: Prerequisites: CS 124 and 131.3 credit hours.<P><h3>Texts</h3><P>Michael J. Quinn. Parallel computing: Theory and practice. Second Edition. McGraw-Hill (1994).<P>Selected references such as papers will be provided.<P><DT><h3>Course Requirements</h3><P>There will be two or three programming assignments on parallelmachines, as well as some written assignments. Participants will presentshort tutorial lectures on a chosen topic. Participants will choose aproject with the instructor's approval, and report the results tothe class.<P><h3>CS 152 Topic Outline</h3>MQ denotes reading pages in Quinn's book.<UL><li>Motivation for parallel computing <b>MQ 1-24</b><ul><li>Response time<li>User concurrency<li>Throughput<li>Fault tolerance<li>Logical structuring</ul><li>Example parallel applications<ul><li>Expression evaluation<li>Matrix computations<li>Database search<li>Sorting</ul><li>Measuring and analyzing parallel program performance<ul><li>Serial vs. parallel time, speedup<li>Efficiency</ul><li>Generic models<ul><li>Theoretically-Motivated Models<ul><li>PRAM (parallel random-access machine) <b>MQ 25-51</b><li>DAG (directed acyclic graph) model<li>WT (work-time) model (JaJa)<li>BSP (bulk-synchronous parallelism)</ul><li>Architecturally-Motivated Models<ul><li>Interconnection Networks <b>MQ 52-89</b><li>MIMD (multiple-instruction-stream, multiple-data-stream)<li>SIMD (single-instruction-stream, multiple-data-stream)<li>SPMD (single-program, multiple-data)</ul><li>Language-Motivated Models<ul><li>Dataflow<li>Systolic arrays<li>Functional programming<li>Logic programming (goal trees)<li>Object-oriented programming</ul></ul><li>Architecture Studies <b>MQ 52-89</b><ul><li>SIMD architectures<ul><li>Connection Machine<li>ICL DAP<li>Masspar</ul><li>MIMD architectures<ul><li>Shared memory<ul><li>Sequent Symmetry<li>Cray T3D</ul><li>Partitioned memory<ul><li>Paragon<li>nCube</ul><li>NUMA (non-uniform memory access machines)<ul><li>BBN butterfly<li>Cedar</ul><li>Clusters</ul><li>Other architectures<ul><li>Dataflow<li>Graph reduction<li>VLIW (very-long instruction word machines)<li>Systolic arrays<li>Neural networks</ul></ul><li>Programming<ul><li>Low-level<ul><li>Review of processes, communication<li>Rendezvous<li>Unix process management<li>Barrier synchronization<li>Mach </ul><li>Higher level<ul><li>Linda<li>Futures<li>APL-like operators</ul></ul><li>Language issues<ul><li>Parallel decomposition<li>Dataflow analysis<li>Grain-size<li>Trace scheduling</ul><li>Languages <b>MQ 91-130</b><ul><li>Concurrent Functional Languages<li>Sisal<li>MultiLisp<li>Fortran 90, High-Performance Fortran<li>Ada 9x<li>Concurrent C<li>*c, *Lisp<li>Concurrent Prolog, Strand<li>PVM, MPI</ul><li>Mapping and scheduling <b>MQ 131-156</b><li>Other System issues<ul><li>Scalability, Isoefficiency metric (Kumar)<li>Cache coherence<li>Combining networks<li>Load balancing<li>Deadlocks<li>Fault tolerance</ul><li>Algorithm Studies<ul><li>Elementary <b>MQ 157-177</b><li>Matrix multiplication <b>MQ 178-197</b><li>Fast Fourier Transform <b>MQ 198-216</b><li>Solving Linear Systems <b>MQ 217-254</b><li>Sorting <b>MQ 255-293</b><li>Parallel Search <b>MQ 294-308</b><li>Graph Algorithms <b>MQ 309-335</b><li>Combinatorial Search <b> MQ 336-366</b></ul><li>Applications and case studies<ul><li>Finite elements<li>Parallel logic programs<li>Monte Carlo traveling salesman problem<li>Many-body simulation<li>Theorem proving</ul><li>Real-Time Systems<ul><li>Characteristics and examples of real-time systems<li>Timing and performance issues<li>Handling time delays and timeouts<li>Deadline specification and scheduling<li>Language requirements</ul><h3>Table of Contents, Parallel Computing: Theory and Practice </h3><ol><li>Introduction<li>PRAM Algorithms<li>Processor Arrays, Multiprocessors, and Multicomputers<li>Parallel Programming Languages<li>Mapping and Scheduling<li>Elementary Parallel Algorithms<li>Matrix Multiplication<li>The Fast Fourier Transform<li>Solving Linear Systems<li>Sorting<li>Dictionary Operations<li>Graph Algorithms<li>Combinatorial Search</ol><h3>Some additional references</h3><ul><li>Joseph JaJa, An introduction to parallel algorithms, Addision-Wesley 1992.<li>Guy E. Blelloch. Vector models for data-parallel computing, MIT Press 1990.<li>Vipin Kumar, et al., Introduction to parallel computing, design and analysis of algorithms, Benjamin/Cummings 1994.<li>Geoffrey Fox, et al., Parallel computing works!, Morgan-Kauffman 1994.<li>Gregory Pfister, In search of clusters, Prentice-Hall 1995.</ul><h3><a name = "www_links">Worldwide Web Links:</a> </h3><ul><li><!WA5><a href = "http://www.cs.cmu.edu/Web/Groups/scandal/www/research-groups.html">Supercomputing and Parallel Computing Research Groups</a></ul></ul> RCS $Id: cs156.html,v 1.2 1996/01/16 19:25:55 keller Exp keller $</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -