This work presents HotSwap, a novel provider-side cold-start optimization for serverless computing. This optimization reduces cold-start time when booting and loading depen-dencies at runtime inside a function container. Previous research has extensively focused on reducing cold-start latency for specific functions. However, little attention has been given to skewed production workloads. In such cases, cross-function optimization becomes essential. Without cross-function optimization, a cloud provider is left with two equally poor options: (i) Either the cloud provider gives up optimization for each function in the long tail (which is slow); or (ii) the cloud provider applies function-specific optimizations (e.g., cache function images) to every function in the long tail (which violates the vendor's cache constraints). HotSwap demonstrates cross-function optimization using a novel pre-warming strategy. In this strategy, a pre-initialized live dependency image is migrated to the new function instance. At the same time, HotSwap respects the provider's cache constraints, because a single pre-warmed dependency image in the cache can be shared among all serverless functions that require that image. HotSwap has been tested on seven representative functions from FunctionBench. In those tests, HotSwap accelerates dependency loading for those serverless functions with large dependency requirements by a factor ranging from 2.2 to 3.2. Simulation experiments using Azure traces indicate that HotSwap can save 88% of space, compared with a previous function-specific method, PreBaking, when sharing a dependency image among ten different functions.

MPI is the de facto standard for parallel computing on a cluster of computers. Checkpointing is an important component in any strategy for software resilience and for long-running jobs that must be executed by chaining together time-bounded resource allocations. This work solves an old problem: a practical and general algorithm for transparent checkpointing of MPI that is both efficient and compatible with most of the latest network software. Transparent checkpointing is attractive due to its generality and ease of use for most MPI application developers. Earlier efforts at transparent checkpointing for MPI, one decade ago, had two difficult problems: (i) by relying on a specific MPI implementation tied to a specific network technology; and (ii) by failing to demonstrate sufficiently low runtime overhead. Problem (i) (network dependence) was already solved in 2019 by MANA's introduction of split processes. Problem (ii) (efficient runtime overhead) is solved in this work. This paper introduces an approach that avoids these limitations, employing a novel topological sort to algorithmically determine a safe future synchronization point. The algorithm is valid for both blocking and non-blocking collective communication in MPI. We demonstrate the efficacy and scalability of our approach through both micro-benchmarks and a set of five real-world MPI applications, notably including the widely used VASP (Vienna Ab Initio Simulation Package), which is responsible for 11% of the workload on the Perlmutter supercomputer at Lawrence Berkley National Laboratory. VASP was previously cited as a special challenge for checkpointing, in part due to its multi-algorithm codes.

Continuous verification and security analysis of software systems are of paramount importance to many organizations. The state-of-the-art for such operations implements agent-based approaches to inspect the provisioned software stack for security and compliance issues. However, this approach, which runs agents on the systems being analyzed, is vulnerable to some attacks, can incur substantial performance impact, and can introduce significant complexity. In this paper, we present the design and prototype implementation of a general-purpose approach for Non-intrusive Software Introspection (NSI). By adhering to NSI, organizations hosting in the cloud can as well control the software introspection workflow with reduced trust in the provider. Experimental analysis of real-world applications demonstrates that NSI presents a lightweight and scalable approach, and has a negligible impact on the performance of applications running on the instance being introspected.

The share of the top 500 supercomputers with NVIDIA GPUs is now over 25% and continues to grow. While fault tolerance is a critical issue for supercomputing, there does not currently exist an efficient, scalable solution for CUDA applications on NVIDIA GPUs. CRAC (Checkpoint-Restart Architecture for CUDA) is a new checkpoint-restart solution for fault tolerance that supports the full range of CUDA applications. CRAC combines: low runtime overhead (approximately 1% or less); fast checkpoint-restart; support for scalable CUDA streams (for efficient usage of all of the thousands of GPU cores); and support for the full features of Unified Virtual Memory (eliminating the programmer's burden of migrating memory between device and host). CRAC achieves its flexible architecture by segregating application code (checkpointed) and its external GPU communication via non-reentrant CUDA libraries (not checkpointed) within a single process's memory. This eliminates the high overhead of inter-process communication in earlier approaches, and has fewer limitations.

Summary The cloud market is nowadays a complex environment where cloud application providers need to maximize their monetary profit and end users look for the most efficient services with the lowest prices. For efficient cloud provisioning, both providers and users should be satisfied in spite of their conflicting needs. Negotiation is the most flexible solution to solve conflicts and enable reaching win‐win agreements. Cloud application provisioning has 2 main properties that highly impact the negotiation decision‐making models: (1) The interdependence between the business layer and the resource layer, and (2) the dynamic provisioning context (eg, negotiators’ preferences and application scheduler). Despite the importance of these 2 properties, the current negotiation models do not take these properties into account. This paper addresses both issues. We propose a multilayer negotiation framework, which also encompasses the potential for dynamic provisioning context. For that, we propose, first, a generic negotiation model dedicated to cloud provisioning. And second, we present its instantiation among cloud layers for efficient SaaS provisioning, to maximize provider profit and increase user satisfaction. The experiments show the benefits of adding negotiation to the provisioning process by improving it for provider profit, number of accepted requests, and client satisfaction.

Transparently checkpointing MPI for fault tolerance and load balancing is a long-standing problem in HPC. The problem has been complicated by the need to provide checkpoint-restart services for all combinations of an MPI implementation over all network interconnects. This work presents MANA (MPI-Agnostic Network-Agnostic transparent checkpointing), a single code base which supports all MPI implementation and interconnect combinations. The agnostic properties imply that one can checkpoint an MPI application under one MPI implementation and perhaps over TCP, and then restart under a second MPI implementation over InfiniBand on a cluster with a different number of CPU cores per node. This technique is based on a novel "split-process" approach, which enables two separate programs to co-exist within a single process with a single address space. This work overcomes the limitations of the two most widely adopted transparent checkpointing solutions, BLCR and DMTCP/InfiniBand, which require separate modifications to each MPI implementation and/or underlying network API. The runtime overhead is found to be insignificant both for checkpoint-restart within a single host, and when comparing a local MPI computation that was migrated to a remote cluster against an ordinary MPI computation running natively on that same remote cluster.

Unified Virtual Memory (UVM) was recently introduced with CUDA version 8 and the Pascal GPU. The older CUDA programming style is akin to older large-memory UNIX applications which used to directly load and unload memory segments. Newer CUDA programs have started taking advantage of UVM for the same reasons of superior programmability that UNIX applications long ago switched to assuming the presence of virtual memory. Therefore, checkpointing of UVM has become increasing important, especially as NVIDIA CUDA continues to gain wider popularity: 87 of the top 500 supercomputers in the latest listings use NVIDIA GPUs, with a current trend of ten additional NVIDIA-based supercomputers each year. A new scalable checkpointing mechanism, CRUM (Checkpoint-Restart for Unified Memory), is demonstrated for hybrid CUDA/MPI computations across multiple computer nodes. The support for UVM is particularly attractive for programs requiring more memory than resides on the GPU, since the alternative to UVM is for the application to directly copy memory between device and host. Furthermore, CRUM supports a fast, forked checkpointing, which mostly overlaps the CUDA computation with storage of the checkpoint image in stable storage. The runtime overhead of using CRUM is 6% on average, and the time for forked checkpointing is seen to be a factor of up to 40 times less than traditional, synchronous checkpointing.

Large-scale applications rely on resilience mechanisms such as checkpoint-restart to make forward progress in the presence of failures. Unfortunately, this incurs huge I/O overhead and impedes productivity. To mitigate this challenge, this paper introduces a new technique, Shiraz, which demonstrates how to exploit differences in the checkpointing overhead among applications and knowledge of temporal characteristics of failures to improve both the overall system throughput and performance of individual applications.

Existing bare-metal cloud services that provide users with physical servers have a number of serious disadvantages over their virtual alternatives, including slow provisioning times, difficulty for users to release servers (physical machines) and then reuse them to handle changes in demand, and poor tolerance to failures. We introduce M2, a bare-metal cloud service that uses network-mounted boot drives to overcome these disadvantages. We describe the architecture and implementation of M2 and compare its agility, scalability and performance to existing systems. We show that M2 can reduce provisioning time by over 50% while offering richer functionality, and comparable run time performance with respect to tools that provision images into local disks. M2 is open source and available at https://github.com/CCI-MOC/ims.

System-level checkpoint-restart is a critical technology for long-running jobs in high-performance computing. Yet, only two approaches to checkpointing MPI applications continue to survive in wide use today. One approach is to use the kernel module-based BLCR in combination with an MPI checkpoint-restart service particular to the MPI implementation in use. Unfortunately, this lacks support for some important Linux system services such as SysV IPC (e.g., shared memory objects). A second approach has been to use the original 2009 DMTCP implementation (herein referred to as DMTCP-09) for transparent, system-level checkpointing. Unfortunately, DMTCP-09 lacked support for checkpointing many of the necessary features found by MPI in a modern batch environment. These include: ssh, the InfiniBand network, process migration (restarting an MPI application on different cluster nodes), and modified file path prefixes on restart (typically due to a changing current directory, mount points, library paths, etc.). This work presents DMTCP-PV, a new user-space transparent checkpointing system based on the concept of process virtualization. This approach separately models the state of each local or distributed subsystem while decoupling it from the core checkpointing engine. By separating these concerns, a domain expert can extend checkpointing into a new domain without any knowledge of the core checkpointing engine. This allowed DMTCP-PV to address the deficiencies noted above and many others. It is shown that the runtime overhead of DMTCP-PV is generally less than 1%, and the checkpointing time is dominated by the time to write an image file to stable storage.

Fault tolerance for the upcoming exascale generation has long been an area of active research. One of the components of a fault tolerance strategy is checkpointing. Petascale-level checkpointing is demonstrated through a new mechanism for virtualization of the InfiniBand UD (unreliable datagram) mode, and for updating the remote address on each UD-based send, due to lack of a fixed peer. Note that InfiniBand UD is required to support modern MPI implementations. An extrapolation from the current results to future SSD-based storage systems provides evidence that the current approach will remain practical in the exascale generation. This transparent checkpointing approach is evaluated using a framework of the DMTCP checkpointing package. Results are shown for HPCG (linear algebra), NAMD (molecular dynamics), and the NAS NPB benchmarks. In tests up to 32,752 MPI processes on 32,752 CPU cores, checkpointing of a computation with a 38 TB memory footprint in 11 minutes is demonstrated. Runtime overhead is reduced to less than 1%. The approach is also evaluated across three widely used MPI implementations.

Typical devices of the Internet of Things are usually under-powered, and have limited RAM. This is due to energy and cost concerns. Yet, IoT applications require increasingly complex programs with increasingly large amounts of data. In principle, an application could manage the increasing data within the limited RAM by saving and loading data from the file system as needed. But managing the use of RAM in this way is both time-consuming and error-prone for the code developer. We propose instead a novel architecture in which different semantic scenes are implemented as independent operating system processes. As the need arises to switch from one scene to another, the currently running process, which represents the current scene, is checkpointed and a process representing the new scene is restarted from a checkpoint image. This solution employs checkpointing to provide a simpler framework for the end programmer, while at the same time resulting in higher performance. For example, experiments show that restarting an old process from a checkpoint image is about 25 times faster than starting a new process. When using an mmap-based optimization (deferring the paging in of virtual memory pages until runtime), restarting an old process is about 500 times faster. Overall, checkpoint and restart each execute in less than 0.2 seconds on a Raspberry Pi B.

Software-as-a-Service (SaaS) providers offer on-demand, highly scalable applications to the end users. To maximize their profit, the providers must make profit-aware scheduling decisions about assigning client requests to virtual resources, while respecting the agreed upon Service-Level Agreement (SLA). Given the highly dynamic nature of the cloud environment, unexpected events may affect the initial scheduling plans, which leads to unanticipated SLA violations. Thus, an unaccounted event may create a lose-lose situation between provider and client. If the SLA is violated the provider must pay the potentially high penalty that is negotiated within the original SLA. But from the client's viewpoint, an SLA violation may cause cancellation of a business-critical job, and no ordinary SLA penalty can compensate for the loss of the client's business. The provider's reputation could also suffers as the number of such SLA violations grows, resulting in loss of future clients. On the contrary of most existing work that assume that once established the SLA cannot be modified, we propose to convert the lose-lose situation into a win-win one through an automated renegotiation mechanism. When an event threatens a lose-lose violation of the SLA, the renegotiation mechanism is launched to establish a new SLA that limits the losses on the two sides. Experiments show that this new approach minimizes the loss in profit of the provider and minimizes the number of cancelled jobs experienced by the client, as compared with enforcing the original SLA.

A non-invasive, cloud-agnostic approach is demonstrated for extending existing cloud platforms to include checkpoint-restart capability. Most cloud platforms currently rely on each application to provide its own fault tolerance. A uniform mechanism within the cloud itself serves two purposes: (a) direct support for long-running jobs, which would otherwise require a custom fault-tolerant mechanism for each application, and (b) the administrative capability to manage an over-subscribed cloud by temporarily swapping out jobs when higher priority jobs arrive. An advantage of this uniform approach is that it also supports parallel and distributed computations, over both TCP and InfiniBand, thus allowing traditional HPC applications to take advantage of an existing cloud infrastructure. Additionally, an integrated health-monitoring mechanism detects when long-running jobs either fail or incur exceptionally low performance, perhaps due to resource starvation, and proactively suspends the job. The cloud-agnostic feature is demonstrated by applying the implementation to two very different cloud platforms: Snooze and Open Stack. The use of a cloud-agnostic architecture also enables, for the first time, migration of applications from one cloud platform to another.

Transparently saving the state of the InfiniBand network as part of distributed checkpointing has been a long-standing challenge for researchers. The lack of a solution has forced typical MPI implementations to include custom checkpoint-restart services that "tear down" the network, checkpoint each node in isolation, and then re-connect the network again. This work presents the first example of transparent, system-initiated checkpoint-restart that directly supports InfiniBand. The new approach simplifies current practice by avoiding the need for a privileged kernel module. The generality of this approach is demonstrated by applying it both to MPI and to Berkeley UPC (Unified Parallel C), in its native mode (without MPI). Scalability is shown by checkpointing 2,048 MPI processes across 128 nodes (with 16 cores per node). The run-time overhead varies between 0.8% and 1.7%. While checkpoint times dominate, the network-only portion of the implementation is shown to require less than 100 milliseconds (not including the time to locally write application memory to stable storage).

The ability to easily deploy parallel computations on the Cloud is becoming ever more important. The first uniform mechanism for checkpointing a network of virtual machines is described. This is important for the parallel versions of common productivity software. Potential examples of parallelism include Simulink for MATLAB, parallel R for the R statistical modelling language, parallel blast.py for the BLAST bioinformatics software, IPython.parallel for Python, and GNU parallel for parallel shells. The checkpoint mechanism is implemented as a plugin in the DMTCP checkpoint-restart package. It operates on KVM/QEMU, and has also been adapted to Lguest and pure user-space QEMU. The plugin is surprisingly compact, comprising just 400 lines of code to checkpoint a single virtual machine, and 200 lines of code for a plugin to support saving and restoring network state. Incremental checkpoints of the associated virtual filesystem are accommodated through the Btrfs filesystem. Experiments demonstrate checkpoint times of a fraction of a second by using forked checkpointing, mmap-based restart, and incremental Btrfs-based snapshots.

Abstracts of the invited speaker talks Modeling, Global Constraints, and Decomposition by J. Christopher Beck and Applications of Graph Search in Group Theory and Proteomics by Gene Cooperman, presented that the 2013 SoCS Symposium.

A common programmer experience is to execute a long-running computation only to see a bug crash the program after hours or days. While it is often easy to capture a "buggy" expression value at the point of the crash, it is less easy to discover the point in the program where the expression became buggy. For such "difficult" bugs, this work presents an automated tool based on binary search through a process lifetime. The tool operates both in single-threaded and multi-threaded program. The underlying algorithm depends on on checkpoints, deterministic replay, and decomposition of debugging histories. The tool is scalable in the sense that the running time is a small constant factor beyond the standalone running time. Further, it requires only a logarithmic number of probes of the expression value --- an advantage when the time to execute the expression is large. The algorithm is demonstrated for such real-world programs as MySQL.

In cluster computing, power and cooling represent a significant cost compared to the hardware itself. This is of special concern in the cloud, which provides access to large numbers of computers. We examine the use of ARM-based clusters for low-power, high performance computing. This work examines two likely use-modes: (i) a standard dedicated cluster, and (ii) a cluster of pre-configured virtual machines in the cloud. A 40-node department-level cluster based on an ARM Cortex-A9 is compared against a similar cluster based on an Intel Core2 Duo, in contrast to a recent similar study on just a 4-node cluster. For the NAS benchmarks on 32-node clusters, ARM was found to have a power efficiency ranging from 1.3 to 6.2 times greater than that of Intel. This is despite Intel's approximately five times greater performance. The particular efficiency ratio depends primarily on the size of the working set relative to L2 cache. In addition to energy-efficient computing, this study also emphasizes fault tolerance: an important ingredient in high performance computing. It relies on two recent extensions to the DMTCP checkpoint-restart package. DMTCP was extended (i) to support ARM CPUs, and (ii) to support check pointing of the Qemu virtual machine in user-mode. DMTCP is used both to checkpoint native distributed applications, and to checkpoint a network of virtual machines. This latter case demonstrates the ability to deploy pre-configured software in virtual machines hosted in the cloud, and further to migrate cluster computation between hosts in the cloud.

Graphics Processing Units (GPUs) are becoming the workhorse of scalable computations. MADNESS is a scientific framework used especially for computational chemistry. Most MADNESS applications use operators that involve many small tensor computations, resulting in a less regular organization of computations on GPUs. A single GPU kernel may have to multiply by hundreds of small square matrices (with fixed dimension ranging from 10 to 28). We demonstrate a scalable CPU-GPU implementation of the MADNESS framework over a 500-node partition on the Titan supercomputer. For this hybrid CPU-GPU implementation, we observe up to a 2.3-times speedup compared to an equivalent CPU-only implementation with 16 cores per node. For smaller matrices, we demonstrate a speedup of 2.2-times by using a custom CUDA kernel rather than a cuBLAS-based kernel.

In order to keep up with the demand for solutions to problems with ever-increasing data sets, both academia and industry have embraced commodity computer clusters with locally attached disks or SANs as an inexpensive alternative to supercomputers. With the advent of tools for parallel disks programming, such as MapReduce, STXXL and Roomy --- that allow the developer to focus on higher-level algorithms --- the programmer productivity for memory-intensive programs has increased many-fold. However, such parallel tools were primarily targeted at iterative programs.

Reversible debuggers have existed since the early 1970s. A novel approach, URDB, is introduced based on checkpoint/re-execute. It adds reversibility to a debugger, while still placing the end user within the familiar environment of their preferred debugger. The URDB software layer currently includes modes that understand the syntax for four debuggers: GDB for C/C++/Java/Fortran, Python (pdb), MATLAB, and Perl (perl -d). It does so by adding a thin URDB software layer on top of the DMTCP checkpoint-restart package. URDB passes native debugging commands between the end user and the underlying debugging session. URDB models the four common debugging primitives that form the basis for most debuggers: step, next, continue, break. For example, given a debugging history of the form [step, next, step], URDB's reverse-step produces a new history, [step, next]. Further, subtle algorithms are described for reverse-xxx. For example, reverse-step operates correctly when the last instruction of the history is next or continue.

Permutation multiplication (or permutation composition) is perhaps the simplest of all algorithms in computer science. Yet for large permutations, the standard algorithm is not the fastest for disk or for flash, and surprisingly, it is not even the fastest algorithm for RAM on recent multi-core CPUs. On a recent commodity eight-core machine we demonstrate a novel algorithm that is 50% faster than the traditional algorithm. For larger permutations on flash or disk, the novel algorithm is orders of magnitude faster. A disk-parallel algorithm is demonstrated that can multiply two permutations with 12.8 billion points using 16 parallel local disks of a cluster in under one hour. Such large permutations are important in computational group theory, where they arise as the result of the well-known Todd-Coxeter coset enumeration algorithm. The novel algorithm emphasizes several passes of streaming access to the data instead of the traditional single pass using random access to the data. Similar novel algorithms are presented for permutation inverse and permutation multiplication by an inverse, thus providing a complete library of the underlying permutation operations needed for computations with permutation groups.

DMTCP (distributed multithreaded checkpointing) is a transparent user-level checkpointing package for distributed applications. Checkpointing and restart is demonstrated for a wide range of over 20 well known applications, including MATLAB, Python, TightVNC, MPICH2, OpenMPI, and runCMS. RunCMS runs as a 680 MB image in memory that includes 540 dynamic libraries, and is used for the CMS experiment of the Large Hadron Collider at CERN. DMTCP transparently checkpoints general cluster computations consisting of many nodes, processes, and threads; as well as typical desktop applications. On 128 distributed cores (32 nodes), checkpoint and restart times are typically 2 seconds, with negligible run-time overhead. Typical checkpoint times are reduced to 0.2 seconds when using forked checkpointing. Experimental results show that checkpoint time remains nearly constant as the number of nodes increases on a medium-size cluster. DMTCP automatically accounts for fork, exec, ssh, mutexes/ semaphores, TCP/IP sockets, UNIX domain sockets, pipes, ptys (pseudo-terminals), terminal modes, ownership of controlling terminals, signal handlers, open file descriptors, shared open file descriptors, I/O (including the readline library), shared memory (via mmap), parent-child process relationships, pid virtualization, and other operating system artifacts. By emphasizing an unprivileged, user-space approach, compatibility is maintained across Linux kernels from 2.6.9 through the current 2.6.28. Since DMTCP is unprivileged and does not require special kernel modules or kernel patches, DMTCP can be incorporated and distributed as a checkpoint-restart module within some larger package.

Centralizers are an important tool in in computational group theory. Yet for large matrix groups, they tend to be slow. We demonstrate a O(√|G|(1/logε)) black box randomized algorithm that produces a centralizer using space logarithmic in the order of the centralizer, even for typical matrix groups of order 1020 . An optimized version of this algorithm (larger space and no longer black box) typically runs in seconds for groups of order 1015 and minutes for groups of order 1020. Further, the algorithm trivially parallelizes, and so linear speedup is achieved in an experiment on a computer with four CPU cores. The novelty lies in the use of a biased tadpole, which delivers an order of magnitude speedup as compared to the classical tadpole algorithm. The biased tadpole also allows a test for membership in a conjugacy class in a fraction of a second. Finally, the same methodology quickly finds the order of a matrix group via a vector stabilizer. This allows one to eliminate the already small possibility of error in the randomized centralizer algorithm.

The number of moves required to solve any state of Rubik's cube has been a matter of long-standing conjecture for over 25 years -- since Rubik's cube appeared. This number is sometimes called "God's number". An upper bound of 29 (in the face-turn metric) was produced in the early 1990's, followed by an upper bound of 27 in 2006.

Through the use of a new disk-based method for enumerating very large orbits, condensation for orbits with tens of billions of elements can be performed. The algorithm is novel in that it offers efficient access to data using distributed disk-based data structures. This provides fast access to hundreds of gigabytes of data,which allows for computing without worrying about memory limitations.

We present a transparent, system-level checkpointing solution for master-worker parallelism that automatically adapts, upon restart, to the number of processor nodes available. This is important, since nodes in a cluster fail. It also allows one to adapt to using multiple cluster partitions and multiple resources from the computational grid, as they become available. Checkpointing a master-worker computation has the additional advantage of needing to checkpoint only the master process. This is both fast and more economical of disk space. This has been demonstrated by checkpointing Geant4, a million line C++ program. Our solution has been implemented in the context of TOP-C (task oriented parallel C/C++), a free, open-source parallel package, although it can easily be ported to additional master-worker packages.

This poster paper summarizes our solution for mining max frequent generalized itemsets (g-itemsets), a compact representation for frequent patterns in the generalized environment.

We outline a distributed, disk-based technique for computing over very large matrix groups. This technique is used to compute a permutation representation for the Baby Monster, a sporadic simple group that acts on 13,571,955,000 points. Its group order is approximately 4 × 1033. This is a landmark because it is 100 times larger than any previous construction of a permutation representation. By using the computed on-disk data structures, computation over the Baby Monster is now feasible using the distributed disks of a cluster. Our work allows researchers to use either a matrix, a permutation, or a word representation for computing over the Baby Monster where previously only a matrix representation was available. The methodology is demonstrated by using as a signature the image of a vector that is stabilized by the maximal subgroup. The technique extends to finite simple groups and to other groups, through other signatures.

Geant4 is a very large, highly accurate toolkit for Monte Carlo simulation of particle-matter interaction. It has been applied to high-energy physics, cosmic ray modeling, radiation shields, radiation therapy, mine detection, and other areas. Geant4 is being used to help design some high energy physics experiments (notably CMS and Atlas) to be run on the future large hadron collider: the largest particle collider in the world. The parallelization, ParGeant4, represents a challenge due to the unique characteristics of Geant4: (i) complex object-oriented design; (ii) intrinsic use of templates and abstract classes to be instantiated later by the end user; (iii) large program with many developers; and (iv) frequent releases. The key issue for parallelization is not just how to parallelize "correctly" but also how to parallelize "with minimum effort". In addition, the parallelization should make as few assumptions about the source code as possible, due to the frequent release schedule of Geant4. We use TOP-C (Task Oriented Parallel C/C++) for parallelization and Marshalgen for marshaling/ serialization. In some examples on a cluster of 100 nodes yielded a speedup of up to 94.4. The code’s portability, scalability and performance are also discussed.

We present a transparent, system-level checkpointing solution for master-worker parallelism that automatically adapts, upon restore, to the number of processor nodes available. We call this adaptive checkpointing. This is important, since nodes in a cluster fail. It also allows one to adapt to using mutliple cluster partitions, as they become available. Checkpointing a master-worker computation has the additional advantage of needing to checkpoint only the master process. This is both fast (0.05 s in our case), and more economical of disk space. We describe a system-level solution. The application writer does not declare what data structures to checkpoint. Furthermore, the solution is transparent. The application writer need not add code to request a checkpoint at appropriate locations. The system-level strategy avoids the labor-intensive and error-prone work of explicitly checkpointing the many data structures of a large program

Data intensive applications on clusters often require requests quickly be sent to the node managing the desired data. In many applications, one must look through a sorted tree structure to determine the responsible node for accessing or storing the data. Examples include object tracking in sensor networks, packet routing over the Internet, request processing in publish-subscribe middleware, and query processing in database systems. When the tree structure is larger than the CPU cache, the standard implementation potentially incurs many cache misses for each lookup; one cache miss at each successive level of the tree. As the CPU-RAM gap grows, this performance degradation will only become worse in the future. We propose a solution that takes advantage of the growing speed of local area networks for clusters. We split the sorted tree structure among the nodes of the cluster. We assume that the structure will fit inside the aggregation of the CPU caches of the entire cluster. We then send a word over the network (as part of a larger packet containing other words) in order to examine the tree structure in another node's CPU cache. We show that this is often faster than the standard solution, which locally incurs multiple cache misses while accessing each successive level of the tree. The principle is demonstrated with a cluster configured with Pentium III nodes connected with a Myrinet network. The new approach is shown to be 50% faster on this current cluster. In the future, the new approach is expected to have a still greater advantage as networks grow in speed, and as cache lines grow in length (greater cache miss penalty). This can be used to successfully overcome the inherent memory latency associated with cache misses

Group membership is a fundamental algorithm, upon which most other algorithms of computational group theory depend. Until now, group membership for permutation groups has been limited to ten million points or less. We extend the applicability of group membership algorithms to permutation groups acting on more than 100,000,000 points. As an example, we experimentally construct a group membership data structure for Thompson's group, acting on 143,127,000 points, in 36 minutes. More significantly, we require approximately 10 GB of RAM for the computation --- even though a single permutation of Thompson's group already requires half a gigabyte of storage.In addition, we propose a disk-based group membership algorithm with the promise of extending group membership to well over one billion (1,000,000,000) points. Such a disk-based algorithm has formerly been impossible, due in part to the lack of a practical disk-based algorithm for multiplying and taking inverses of such large permutations. Random access to disk is prohibitively expensive. We demonstrate the first practical disk-based implementation of the basic permutation operations. We also propose a disk-based architecture for group membership data structures.

Porting large applications to distributed computing platforms is a challenging task from a software engineering perspective. The Computational Grid has gained tremendous popularity as it aggregates unprecedented amounts of compute and storage resources by means of increasingly high performance network technology. The primary aim of this paper is to demonstrate how the development time to port very large applications to this environment can be significantly reduced. TOP-C and AMPIC are software packages that have each seen successful application in their respective domains of parallel computing and process creation/communication. We combine them to implement and deploy a master-worker model of parallel computing over the Computational Grid. To demonstrate the benefit of our approach, we ported the 1,000,000 line Geant4 sequential code in three man-weeks by using our TOP-C/AMPIC integration. This paper evaluates the benefits of our approach from a software engineering perspective, and presents experimental results obtained with the new implementation of Geant4 on a Grid testbed.

Several researchers have worked on parallel coset enumeration strategies using shared memory. This is important not only for speed, but also because the large memory requirements of coset enumeration often make memory the dominant cost, and this cost can be reduced by using many CPU's to reduce the time during which this memory must be “rented”. We take as our testbed an enumeration of Lyons's group (approximately 8.87 million cosets). Lyons's group is one of the largest enumerations carried out in the literature. Previous enumerations of this group in the literature do not appear to scale well as the number of processors increase, with speedups such as a factor of 2 using 4 processors and a speedup of 4 using 16 processors. By using what we call bulk definition of cosets, we achieve nearly linear speedup of the parallel portion of our program. This result depends on two new heuristics for bulk coset definition, clouds and prescan, and a theorem showing that when using parallelized bulk coset definition, the enumeration, including the order in which cosets are defined, is independent of the number of processors used for parallelization. A total computation of 9.4 hours = 473 min. (clouds phase) + 41 min. (prescan phase) is reduced using 32 processors to 23 min. (clouds, par.) + 50 min. (clouds, seq.) + 41 min. (prescan). Parallel timings are presented for the clouds phase, while the prescan phase will be parallelized at a later date. The parallelization of our coset enumeration software was achieved using TOP-C. Some of these ideas may also be useful in parallelizations of related algorithms, such as Grobner bases and Knuth-Bendix.

A parallel variamt of breadth-first search for distributed computing is presented.The variant allows exhaustive enumeration of elements of a search space (implicitly defined graph) in which the representation of all graph nodes would otherwise require more than the total available memory.This algorithm requires the use of a tadpole data structure to partition the sezwch space into connected subgraphs, with each subgraph stored within the memory of a single processor.Thus, the graph of the nodes are stored in a way that adds greater spatial locidity, thereby reducing communication among processors.The algorithm enumerates the tadpoles in a breadth-first manner while executing depth-first search within each tadpole.The search within each tadpole is reduced to tree search.A parameter is defined that allows a linear tradeoff in which memory and communication are each reduced linearly as CPU time grows.The result appears to fill a gap in the literature.which has concentrated on parallel depth-first search, but has been relatively sparse in the case of parallel breadth-first search.

The goal of this work is to simplify parallel application development, and thus ease the learning barriers faced by non-experts. It is especially useful where there is little data-parallelism to be recognized by a compiler. The applications programmer need learn the intricacies of only one primary subroutine in order to get the full benefits of the parallel interface. The applications programmer defines a high level concept, the task, that depends only on his application, and not on any particular parallel library. The task is defined by its three phases: (a) the task input, (b) sequential code to execute the task, and (c) any modifications of global variables that occur as a result of the task. In particular, side effects (which change global variable values) must not occur in phase (b). Forcing the user to re-organize his computation in these terms allows us to present the applications programmer with a single global environment visible to all processors (whether on a SMP or a NOW architecture), in the context of a masterslave architecture. Both a shared memory implementation (running on an SGI or SUN Solaris architecture) and a NOW memory implementation (running on top of MPI) are described. The implementations were tested by a naive program for integer factorization, and by a more sophisticated Todd-Coxeter coset enumeration. Integer factorization was chosen so as to exercise the major features of TOP-C in an unambiguous context.

Article Free Access Share on New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique Authors: Gene Cooperman College of Computer Science, Northeastern University, Boston, MA College of Computer Science, Northeastern University, Boston, MAView Profile , Michael Tselman College of Computer Science, Northeastern University, Boston, MA College of Computer Science, Northeastern University, Boston, MAView Profile Authors Info & Claims ISSAC '96: Proceedings of the 1996 international symposium on Symbolic and algebraic computationOctober 1996 Pages 155–160https://doi.org/10.1145/236869.236927Published:01 October 1996Publication History 14citation171DownloadsMetricsTotal Citations14Total Downloads171Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Many users of symbolic algebra systems have felt the need for greater CPU power.Yet few of them have ventured into

Permutation representations constructed from matrix groups defined over finite fields often have very high degree. New techniques are presented for performing effective computations with the resulting permutation group. These techniques are designed to work in an environment in which the degree of the permutation group is considered too large to permit the use of standard permutation algorithms for solving problems such as computing the order of the group and testing simplicity. The theory has been successfully tested on a representation of the sporadic simple group Ly, discovered by Lyons [10]. In [5], a permutation representation was constructed for Ly of degree 9,606,125 on a conjugacy class of subgroups of order 3. Using this permutation representation and no specific knowledge of the group, we are able to apply our methods to construct a base of at most four points for the resulting permutation group, compute its order and verify simplicity. Monte Carlo algorithms for group membership presented in [2] are used to improve the performance of these algorithms.

New techniques, both theoretical and practical, are presented for constructing a permutation representation for a matrix group. We assume that the resulting permutation degree, n, can be 10,000,000 and larger. The key idea is to build the new permutation representation using the conjugation action on a conjugacy class of subgroups of prime order. A unique signature for each group element corresponding to the conjugacy class is used in order to avoid matrix multiplication. The requirement of at least n matrix multiplications would otherwise have made the computation hopelessly impractical. Additional software optimizations are described, which reduce the CPU time by at least an additional factor of 10. Further, a special data structure is designed that serves both as a search tree and as a hash array, while requiring space of only 1.6n log2 n bits.

Article A fast cyclic base change for permutation groups Share on Authors: Gene Cooperman View Profile , Larry Finkelstein View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 224–232https://doi.org/10.1145/143242.143316Online:01 August 1992Publication History 0citation234DownloadsMetricsTotal Citations0Total Downloads234Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Nearly linear time algorithms for permutation groups with a small base Authors: László Babai Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088 Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088View Profile , Gene Cooperman College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Larry Finkelstein College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Ákos Seress Dept. of Mathematics, Ohio State University, Columbus, Ohio Dept. of Mathematics, Ohio State University, Columbus, OhioView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 200–209https://doi.org/10.1145/120694.120724Online:01 June 1991Publication History 19citation320DownloadsMetricsTotal Citations19Total Downloads320Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Fast Monte Carlo algorithms for permutation groups Authors: László Babai Univ. of Chicago, Chicago, IL Univ. of Chicago, Chicago, ILView Profile , Gene Cooperman Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Larry Finkelstein Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Eugene Luks Univ. of Oregon, Eugene Univ. of Oregon, EugeneView Profile , Ákos Seress Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 90–100https://doi.org/10.1145/103418.103435Published:03 January 1991Publication History 14citation519DownloadsMetricsTotal Citations14Total Downloads519Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that each call to Rand(G) takes time O(log(|G|)n). The random base change algorithm has probability 1 -- 1/|G|2 of completing in time O(log2(|G|)n) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering which requires O(log(|G|)n) space and which can be used to test group membership in time O,(log(|G|)n). The time to build a data structure for computing a Rand(G) with the above properties from a strong generating set for G is dominated by the time to construct the strong generating set from the original set of generators.

The construction of point stabilizer subgroups is a problem which has been studied intensively. [1, 4, 5, 10, 11, 12, 14] This work describes a general reduction of certain group constructions to the point stabilizer problem. Examples are given for the centralizer, the normal closure, and a restricted group intersection problem. For the normal closure problem, this work provides an alternative to current algorithms, which are limited by the need for repeated closures under conjugation. For the centralizer and restricted group intersection problems, one can use an existing point stabilizer sequence along with a recent base change algorithm [2] to avoid generating a new point stabilizer sequence. This reduces the time complexity by at least an order of magnitude. Algorithms and theoretical time estimates for the special case of a small base are also summarized. An implementation is in progress.