The Self-Paced Learning Increases Retention and Capacity (SPARC) project is responding to the well-documented surge in CS enrollment by creating a self-paced learning environment that blends online learning, automated assessment, collaborative practice, and peer-supported learning. SPARC delivers educational material online, encourages students to practice programming in groups, frees them to learn material at their own pace, and allows them to demonstrate proficiency at any time. This model contrasts with traditional course offerings, which impose a single schedule of due dates and exams for all students. SPARC allows students to complete courses faster or slower at a pace tailored to the individual, thereby allowing universities to teach more students with the same or fewer resources. This paper describes the goals and elements of the SPARC model as applied to CS1. We present results so far and discuss the future of the project.

Summary form only given. This paper describes the development of a fine-grained meta-heuristic for solving large strip packing problems with guillotine layouts. An architecture-adaptive environment aCe, and the aCe C parallel programming language are used to implement a massively parallel genetic simulated annealing (GSA) algorithm. The parallel GSA combines the temperature schedule of simulated annealing with the crossover and mutation operators that are applied to chromosome populations in genetic algorithms. For our problem, chromosomes are normalized postfix expressions that represent guillotine strip packings. Preliminary results for some benchmark data sets are reported and indicate that the parallel GSA method holds promise as a technique for solving the strip packing problem.

We present a genetic algorithm (GA) that uses a slicing tree construction process for the placement and area optimization of soft modules in very large scale integration floorplan design. We have overcome the serious representational problems usually associated with encoding slicing floorplans into GAs and have obtained excellent (often optimal) results for module sets with up to 100 rectangles. The slicing tree construction process used by our GA to generate the floorplans has a runtime scaling of O(n lg n). This compares very favorably with other recent approaches based on nonslicing floorplans that require much longer runtimes. We demonstrate that our GA outperforms a simulated annealing implementation with the same representation and mutation operators as the GA.

The constrained 2D cutting stock problem is an irregular problem with dynamic data structures, highly variable amounts of computation per task, and unpredictable amounts and patterns of communication. This paper describes the design and implementation of a parallel solution to this problem on a cluster of workstations and a distributed memory multicomputer. The key element of our parallel solution is the replication of an important data structure on all processors. By exploiting properties of the cutting stock problem which allow the use of relaxed consistency mechanisms, our approach is able to reduce the overheads for communication and synchronization in comparison to approaches that partition the data structure among processors. A token-based lazy release consistency protocol is used to ensure mutual exclusion and maintain consistency, and a randomized work-stealing protocol is employed to dynamically balance work among processors. Good speedups are reported for three benchmark problems executed on two distributed memory platforms: a cluster of workstations interconnected by a 10 Mbit/s Ethernet and an Intel Paragon. © 1998 John Wiley & Sons, Ltd.

The paper describes the design and implementation of a solution to the constrained 2D cutting stock problem on a cluster of workstations. The constrained 2D cutting stock problem is an irregular problem with a dynamically modified global data set and irregular amounts and patterns of communication. A replicated data structure is used for the parallel solution since the ratio of reads to writes is known to be large. Mutual exclusion and consistency are maintained using a token based lazy consistency mechanism, and a randomized protocol for dynamically balancing the distributed work queue is employed. Speedups are reported for three benchmark problems executed on a cluster of workstations interconnected by a 10 Mbps Ethernet.

A systolic based parallel approximation algorithm that obtains solutions to the I-D bin packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study demonstrates that the heuristic offers improved packing and execution performance over parallelizations of two well-known serial algorithms.>