High-Performance Java Platform Computing

THOMAS W. CHRISTOPHER and GEORGE K. THIRUVATHUKAL are principals in Tools of Computing LLC, a Chicago-area consulting firm specializing in high-performance computing and object-oriented languages. A professor of Computer Science for over twenty years, Christopher has written several compilers. Thiruvathukal, a former computer scientist at Argonne National Laboratories, is now a visiting professor at Loyola University in Chicago and Secretary General of the Java Grande Group, whose aim is to advance Java-based scientific and technical computing.

1. Foundations.


The von Neumann Machine. Flynn's Taxonomy. Control-Memory Taxonomy. Speedup and Efficiency. Amdahl's Law. Scalability. Problems of Parallelism. Grain Size. Starvation. Deadlock. Flooding and Throttling. Layout. Latency. Scheduling. Programming Techniques. Chapter Wrap-up. Exercises.



2. Threads.


Why Is Multithreading Useful? Overview of the Java Threads Classes. Thread: The Class Responsible for Thread Creation and Execution. Runnable: Making Threads Without Extending the Thread Class. Hello World: A First Example of Multithreading. Implementing Interfaces and Extending Classes: What's the Deal? Concepts. A Little Bit of History. Some Definitions. Multiprogramming vs Multitasking. Concurrency vs Parallelism vs Distribution. Threads vs Processes. Kernel-level vs User-level Threads. Quick Tour of Java Threads Functions. Construction. Daemon Threads. Thread Control. Very Useful Static Methods. Thread Synchronization. Cooperative Multitasking. Prioritized Scheduling. Miscellaneous Status Methods. Methods Not Covered Here. Exercises.



3. Race Conditions and Mutual Exclusion.


Know Your Enemy! Race Conditions. Egoist: A First Study in Race Conditions. A Word on Priorities. What Is a Race Condition? Race0 Class. Critical Sections and Object Locking. Race1 Class-Fixing Race0 with Synchronization. Conditions. Motivating the Need for Conditions. Key Object Methods Needed to Work with Conditions in Java. File Copying: A Producer-Consumer Example. Locks-Binary Semaphores: An Example of Using Conditions. Race2: Reworked Race1 Using Locks. Classic Synchronization Mechanisms. Counting Semaphore. Barrier. Futures. Deadlock. What Is Deadlock? How to Know When Deadlock Has Hit You? Four Conditions of Deadlock. A Classic Example: Dining Philosophers. Chapter Wrap-up. Exercises.



4. Monitors.


Real Monitors and Java Monitors. Class Monitor in the Thread Package. Monitor's Methods. Interface MonitorCondition's Methods. Interface MonitorLock. Examples using Monitor Objects. SimpleFuture. SharedTableOfQueues. Implementation of Monitor, Condition, and MonitorLock. Monitor Entry and Exit. Monitor.Condition. Monitor.Lock. The Multiple Reader-Writer Monitors. Policies. Entering and Leaving the Critical Sections. The Single-Reader-Writer Monitor. The Readers-Preferred Monitor. The Writers-Preferred Monitor. The Alternating Readers-Writers Monitor. The Take-a-Number Monitor. Chapter Wrap-up. Exercises.



5. Parallel Execution of Subroutines in Shared Memory.


Creating and Joining. Example: Trapezoidal Numeric Integration. RunQueue. RunQueue Methods. RunQueue Implementation. Recursive Shell Sort: RunQueues and SimpleFutures. Accumulator. Accumulator Operations. Patterns of Use of Accumulators. Using Accumulators. Numeric Integration. TerminationGroup. Combinatorial Search. The 0-1 Knapsack Problem. Parallel Depth-first Search for the Knapsack Problem. Knapsack2. PriorityRunQueue. Branch-and-Bound with Priority Run Queues. Branch and Bound for 0-1 Knapsack. A Purer Branch-and-Bound 0-1 Knapsack. Chapter Wrap-up. Exercises.



6. Parallelizing Loops.


Chore Graphs. Gathering Chores into Threads. Example: Warshall's Algorithm. Static Scheduling. Dynamic Scheduling. Example: Longest Common Subsequence. Example: Shell Sort. Chapter Wrap-up. Exercises.



7. Chores.


The RunDelayed Interface. Futures. FutureFactory. Chore-programming Techniques. Job Jars. Chore Graphs. Macro Dataflow. Flow of Control. Macro Dataflow Examples: Vector Addition. Continuations to Separate Operand Fetch from Operation. Static Dataflow Style and Storing Operands in Instructions. Fetching in Continuations. Chore examples: Warshall's Algorithm. WarshallDF1 and Warshall's Algorithm in Dataflow. WarshallC1 through WarshallC3: Chores, But Not Dataflow. Chapter Wrap-up. Exercises.



8. Thread and Chore Synchronization.


TerminationGroup. Barrier. BarrierFactory. AccumulatorFactory. Parallel Quicksort. Shell Sort. Chapter Wrap-up.



9. Shared Tables of Queues.


Shared Tables of Queues. Methods. Implementing Synchronizations Using a Shared Table of Queues. Indexed Keys. Implementing More Synchronizations and Shared Structures. Reactive Objects. Communicating through a Shared Table of Queues. Future Queues. Methods. Implementation of FutureQueue. Example of FutureQueue: The Queued Readers-Writers Monitor. Future Tables. Chapter Wrap-up. Exercises.



10. Streams Essentials.


The Streams Abstraction. Building Your Own Stream. Caesar Cipher: Very Basic Encryption. Chapter Wrap-up. Exercises.



11. Networking.


Exploring the Client Side. Services: The Internet Story. Destination Sendmail. Java Networking: Socket and InetAddress. Where Are the Services? A Kind and Gentle Introduction to the Server Side. Iterative Servers. Simple Messaging Architecture. The Message Class. DateService and DateClient SMA Style. Chapter Wrap-Up. Exercises.



12. Coordination.


Generic Mailbox Invocations. GMI: Goals and Design Overview. Callable: An Interface for Accepting Communication. CallMessage: An Abstract Class for Marshalling and Unmarshalling! RemoteCallServer. RemoteCallServerDispatcher. MemoServer. MemoClient. Vector Inner Product. Trapezoidal Integration. Warshall's Algorithm. Chapter Wrap-up. Exercises.



Index.