Brock University
Department of Computer Science
Winter
2010 Instructor: Vlad Wojcik 
Assignments: WARM-UP
COURSE OBJECTIVE:
To familiarize students with basic ideas pertaining to parallel computation. We will depart from the standard architecture of the von Neumann-type digital computer. Parallel computing architectures will be discussed, including SISD, SIMD, MIMD, data flow paradigms. Multiprocessor organizations: arrays, meshes of trees, hypercubes. Dynamic and static reconfiguration. Diameter, bandwidth, and bisection width of the multiprocessor configuration. Parallel algorithms and their performance estimation: big O, Theta and Omega notations. Introduction to the theory of parallel languages with practical exposure to Ada 2005.
Origins of parallelism, classification of algorithm designs, characterization of performance. Pipelined computers: selection and comparison, case studies. Processor arrays, switching networks, case studies. Parallel languages: general principles, parallel constructs, vectorizing compilers, issues of portability. Practical exposure to parallel programming language (Ada 2005) and parallel computing hardware. Parallel algorithms: general principles, recurrences, parallel approach to data structures and computational structures. Future trends: technology, design limitations, future supercomputers.
COSC 2P13 (minimum 60%). NOTE: In case of any discrepancies, the University Calendar prevails.
T.G. Mattson, B.A. Sanders, B.L. Massingill: Patterns for Parallel Programming, Addison-Wesley 2005, ISBN 0-321-22811-1.
- The modeling Process: A Meta-Model
- Measures of Parallelism: Basic Concepts
- Parallel Computers: A Taxonomy
- Parallel Computers: Memories
- Parallel Computers: Interconnect Architectures
- Parallel Computers: Programming Methodology
- Parallel Computers: Benchmarking
- Parallel Computers: Programming Tools
- Parallel Languages: Compositional C++
- S.H. Roosta: Parallel Processing and Parallel Algorithms, Springer Verlag 2000, ISBN 0-387-98716-9
- I. Foster: Designing and Building Parallel Programs, Addison-Wesley Publishing, 1995, ISBN 0-201-57594-9
- M.A. Smith: Object Oriented Programming in Ada 2005
- R. Riehle: Ada Distilled: An Introduction to Ada Programming for Experienced Computer Programmers, AdaWorks Software Engineering 2002
- J. Barnes: Programming in Ada 2005, 2nd ed., Addison-Wesley Publishing, ISBN 0-201-34293-6
- C. Xavier, S.S. Iyengar: Intro. to Parallel Algorithms, Wiley 1998, ISBN 0-471-25182-8
- H.F. Jordan, G. Alaghband: Fundamentals of Parallel Processing, Prentice Hall 2003, ISBN 0-13-901158-7.
- A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing, Addison-Wesley 2ed., 2003, ISBN 0-201-64865-2.
- B.M. Brosgol: Ada-Java comparison, 2000
- Refresher on Semaphores
- Tasking in Ada + a very brief summary!
- Use of Attributes in Ada
- Garbage collection in Ada: programming example
Ambitious students may wish to offer a seminar. (Please peruse the Marking Scheme below for potential rewards). The topic of a seminar is to be approved by the instructor, who also offers consultations in seminar ideas and preparation.
Possible topic suggestions:
- Cluster Connectivity: Quadrics, Myrinet, Infiniband, Dolphinics, etc ...
- Hottest Processors of the Day ...
- Parallel Programming Approaches with one of: UNIX, MPI, Open MP, PCN, PVM, Linda (including C-Linda and/or FORTRAN-Linda), CHARM ...
- Parallel Programming Languages (select one of): Occam, OpenCL, Modula-2, Modula 3, Java, Fortran M, High Performance Fortran, Compositional C++, Data-flow programming in VAL, Functional programming in SISAL, Data parallel programming with C*, Data parallel programming with Fortran 90 ...
- AI and Parallel Processing
- Selected Parallel Search Algorithms
- Selected Parallel Graph Algorithms
- Parallel Programming Approaches with UNIX
- Measuring Computational Performance
- Parallel Computing with MPI
- OSCAR (Open Source Cluster Application Resources)
- Cluster Management (IPMI, etc.)
- Cluster Booting Issues (PXE, etc.)
- Other (please suggest...)
- Andrew Moir: Parallel Evolution, 24 Mar 2010.
Abstract: Overview of the topic, Strategies for Programming AI in Parallel, Optimal Architectures for the specific AI technique, Theoretical improvement in speed/efficiency, Practical examples of speed increases, Example of a parallel AI technique being implimented, Conclusion
- Ryan Renna, OpenCL, 26 Mar 2010.
Abstract: Heterogeneous parallel computation, Introduction to OpenCL, Anatomy of OpenCL, OpenCL Execution Model, OpenCL Memory Model, An Example, OpenGL + OpenCL interaction, The Future, Conclusion
- Adam Stirtan: Parallel Architecture and Implementations on J2ME Embedded Devices, 31 Mar 2010.
Abstract: The Java 2 Platform Micro Edition (J2ME) for embedded devices will be investigated. A presentation will be held to illustrate how mobile devices such as cellular phones, set top boxes and other devices implement J2ME and how concurrency is accomplished within this hardware restricted framework. A detailed implementation will consist of an application for a J2ME phone which in parallel aggregates device information from network, location and device specific services to relay back to an external server. The concurrent server accepts clients and records received data to a relational database for interpretation from a web application.
- Daniel McCarney: Clojure, 07 Apr 2010.
Abstract: Clojure is specifically relevant to this course because it was designed with concurrency in mind. This topic offers a more pragmatic look at concurrency. Clojure compiles to Java bytecode allowing it to run on the JVM and interact with Java libraries. As mentioned early in the course, this means it is ultimately as weak as the JRE in allowing access to the architecture itself, but it makes it a very appealing "concurrent stepping stone" for organizations with a heavy investment in Java.
Clojure's approach to solving some issues we've mentioned in class could be interesting to my classmates. In particular the idea of "Software Transactional Memory". Clojure prevents concurrent memory modifications using an approach modeled after ACID compliant transactions for databases.
- Adam Powell: Nvidia Tesla Personal Super Computer, 09 Apr 2010. (Presentation slides here).
Abstract: Architecture, the development tools and how to go about acquiring training specifically for the use of the Tesla. I would also like to talk about how most of the people in the class with an Nvidia graphics card already has a highly parallel processor ready for them to use and available to make software using multiple cores.
- Adrian Harrington: CUDA: Nvidia Parallel Computing Architecture, 13 Apr 2010.
Abstract: What is CUDA, Background, Uses & Implementation of CUDA, Intro to GPU computing, CUDA programming model, Code examples, Case Studies and Performance comparisons.
- Two Assignments (each @ 15%) 30%
- Midterm Test @ 30%
- Seminar and/or Exam @ 40% (you must score at least 40% here to pass the course!)
CAUTION: The Department reserves the right to scan submissions using electronic means, in order to ensure the originality of students' work.
In case a given mark is perceived unjust or unclear by a student, s/he is encouraged to see the instructor to discuss the issue. Depending on the case s/he is able to make, a mark can be modified. The deadline to contact the instructor on these matters is one week after the mark has been issued. Marks not disputed within this period will be considered final.
Possible lateness in assignment submission is counted in days, each period of a day ending at 4 PM. The penalty for late submission of assignments is 25% up to three days (or a part of a day). After that period the penalty is 100%.
While honest cooperation between students is considered appropriate, the Department considers plagiarism a serious offense. For clarification on these issues you are directed to the statement of Departmental Policies and Procedures.
Instructor: Vlad Wojcik
Revised: 14 April, 2010 0:31 AM
Copyright © 2010 Brock University
