Tuesday, June 3, 2014
Journal Paper on MAKER and Work Queue
Our paper on converting the MAKER bioinformatics analysis from MPI to Work Queue, done in collaboration with the Notre Dame Bioinformatics Laboratory was recently accepted for publication in the International Journal of Bioinformatics Research and Applications.
CCL Papers at CCGrid 2014
Three papers from the CCL were presented at the 2014 IEEE Conference on Cluster, Cloud, and Grid Computing in Chicago:
- Paul Brenner presented a regular paper,
Opportunistic High Energy Physics Computing in User Space with Parrot which shows how we use Parrot to provide transparent access to complex software stacks without requiring a dedicated shared file system. - Olivia Choudhury presented Accelerating Comparative Genomics Workflows in a Distributed Environment with Optimized Data Partitioning at the C4Bio Workshop. This paper explores various strategies for data partitioning in bioinformatics applications; showing that partitioning for parallel execution must be specialized to the objective of the underlying tool.
- Nick Hazekamp presented a poster, Expanding Tasks of Logical Workflows into Independent Workflows for Improved Scalability in which he demonstrated a technique for transparently parallelizing components of a Galaxy workflow using Makeflow.
Monday, May 19, 2014
Toward a Common Model of Highly Concurrent Programming
(This is the short version of a talk I gave at the MTAGS workshop at Supercomputing 2013. See the slides here.)
Historically, highly concurrent programming has been closely associated with high performance computing. Two programming models have been dominant: shared memory machines in which concurrency was expressed via multiple threads, and distributed memory machines in which concurrency was expressed via explicit message passing. It is widely agreed that both of these programming models are very challenging, even for the veteran programmer. In both cases, the programmer is directly responsible for designing the program from top to bottom and handling all of the issues of granularity, consistency, and locality necessary to achieve acceptable performance, with very little help from the runtime or operating systems.
However, a new approach to concurrent programming has been emerging over the last several years, in which the user programs in a much higher level language and relies upon the system to handle many of the challenging underlying details. To achieve this, the program is successively decomposed into simpler representations, such that each layer of the system can gradually adapt it to the hardware available.
The layers can be described as follows:
A (very incomplete) selection of systems that follow this model:
Each layer of the system fulfills a distinct need. The declarative language (DL) at the top is compact, expressive, and easy for end users, but is intractable to analyze in the general case because it may have a high order of complexity, possibly Turing-complete. The DL can be used to generate a (large) directed acyclic graph (DAG) that represents every single task to be executed. The DAG is not a great user-interface language, but it is much more suitable for a system to perform capacity management and optimization because it is a finite structure with discrete components. A DAG executor then plays the graph, dispatching individual tasks as their dependencies are satisfied. The BOT consists of all the tasks that are ready to run, and is then scheduled onto the underlying computer, using the data dependencies made available from the higher levels.
Why bother with this sort of model? It allows us to compare the fundamental capabilities and expressiveness of different kinds of systems. For example, in the realm of compilers, everyone knows that a proper compiler consists of a scanner, a parser, an optimizer, and a code generator. Through these stages, the input program is transformed from a series of tokens to an abstract syntax tree, an intermediate representation, and eventually to assembly code. Not every compiler uses all of these stages, much less the same code, but by using a common language, it is helpful to understand, compare, and design new systems.
Historically, highly concurrent programming has been closely associated with high performance computing. Two programming models have been dominant: shared memory machines in which concurrency was expressed via multiple threads, and distributed memory machines in which concurrency was expressed via explicit message passing. It is widely agreed that both of these programming models are very challenging, even for the veteran programmer. In both cases, the programmer is directly responsible for designing the program from top to bottom and handling all of the issues of granularity, consistency, and locality necessary to achieve acceptable performance, with very little help from the runtime or operating systems.
However, a new approach to concurrent programming has been emerging over the last several years, in which the user programs in a much higher level language and relies upon the system to handle many of the challenging underlying details. To achieve this, the program is successively decomposed into simpler representations, such that each layer of the system can gradually adapt it to the hardware available.
The layers can be described as follows:
- A declarative language (DL) for compactly representing a complete program.
- A directed graph (DAG) to represent the expanded program and its resources.
- A bag of independent tasks (BOT) with explicit input and output dependencies.
- A shared-nothing cluster to which data and tasks must be assigned.
A (very incomplete) selection of systems that follow this model:
| Layer | Cloud Stack | Workflow Stack | HPC Stack |
| Declarative Language (DL) | Pig | Weaver | Swift-T |
| Directed Acyclic Graph (DAG) | Map-Reduce | Makeflow | - |
| Bag of Tasks (BOT) | JobTracker | Work Queue Master | Turbine |
| Distributed Data | HDFS | Work Queue Workers | MPI |
Each layer of the system fulfills a distinct need. The declarative language (DL) at the top is compact, expressive, and easy for end users, but is intractable to analyze in the general case because it may have a high order of complexity, possibly Turing-complete. The DL can be used to generate a (large) directed acyclic graph (DAG) that represents every single task to be executed. The DAG is not a great user-interface language, but it is much more suitable for a system to perform capacity management and optimization because it is a finite structure with discrete components. A DAG executor then plays the graph, dispatching individual tasks as their dependencies are satisfied. The BOT consists of all the tasks that are ready to run, and is then scheduled onto the underlying computer, using the data dependencies made available from the higher levels.
Why bother with this sort of model? It allows us to compare the fundamental capabilities and expressiveness of different kinds of systems. For example, in the realm of compilers, everyone knows that a proper compiler consists of a scanner, a parser, an optimizer, and a code generator. Through these stages, the input program is transformed from a series of tokens to an abstract syntax tree, an intermediate representation, and eventually to assembly code. Not every compiler uses all of these stages, much less the same code, but by using a common language, it is helpful to understand, compare, and design new systems.
Friday, February 14, 2014
Visualizing 10,000 Cores in Condor
Our Condor pool at the University of Notre Dame has been slowly growing, in no small part due to our collaboration with the Center for Research Computing, where it is now scavenging unused cycles from HPC clusters at the CRC. When the dedicated batch system leaves a node unused, Condor is started on that node and keeps going until the dedicated system wants the node back. Depending on the time of year, that leaves anywhere between 4K and 10K nodes available in the Condor pool.
We have tried a number of approaches at visualizing this complex system over the years. Our latest tool, the Condor Matrix Display started as a summer project by Nick Jaeger, a student from the University of Wisconsin at Eau Claire. The display shows a colored bar for each slot in the pool, where the width is proportional to the number of cores.
With a quick glance, you can see how many users are busy and whether they are running "thin" (1 core) or "fat" (many core) jobs. Sorting by the machine name gives you sense of how each sub-cluster in the pool is used:
While sorting by users gives you a sense of what users are dominating the pool:
The display is always a nice way of viewing the relatively new feature of "dynamic slot" in Condor. A large multi-core machine is now represented as a single slot with multiple resources. For example, this bit of the display shows a cluster of 8-core machines where some of the machines are unclaimed (green), some are running 4-core jobs (blue), and some are running 1-core jobs (green):
We have tried a number of approaches at visualizing this complex system over the years. Our latest tool, the Condor Matrix Display started as a summer project by Nick Jaeger, a student from the University of Wisconsin at Eau Claire. The display shows a colored bar for each slot in the pool, where the width is proportional to the number of cores.
With a quick glance, you can see how many users are busy and whether they are running "thin" (1 core) or "fat" (many core) jobs. Sorting by the machine name gives you sense of how each sub-cluster in the pool is used:
While sorting by users gives you a sense of what users are dominating the pool:
The display is always a nice way of viewing the relatively new feature of "dynamic slot" in Condor. A large multi-core machine is now represented as a single slot with multiple resources. For example, this bit of the display shows a cluster of 8-core machines where some of the machines are unclaimed (green), some are running 4-core jobs (blue), and some are running 1-core jobs (green):
Monday, November 18, 2013
CCL Papers at Supercomputing 2013
Members of the CCL team presented several papers at Supercomputing 2013 in Denver, Colorado:
- Casey Robinson presented Automated Packaging of Bioinformatics Workflows for Portability and Durability Using Makeflow at the Workshop on Scientific Workflows (WORKS).
- Patrick Donnelly presented Design of an Active Storage Cluster Filesystem for DAG Workflows at the Workshop on Data Intensive Computing Systems (DISCS).
- Prof. Thain gave the opening talk, Toward a Common Model of Highly Concurrent Applications at the Workshop on Many Task Computing on Clusters, Grids, and Supercomputers (MTAGS).
Friday, October 11, 2013
CCL Workshop October 10-11 at Notre Dame
Join us for the annual CCL workshop at the University of Notre Dame!
http://www.nd.edu/~ccl/workshop/2013
The workshop is an opportunity for beginners and experts alike to learn about the latest software release, get to know the CCL team, meet other people engaged in large scale scientific computing, and influence the direction of our research and development.
Thursday, October 10th
Afternoon: Introduction and Software Tutorials
Friday, October 11th
All Day: New Technology, Scientific Talks, and Discussion
There is no registration fee, however, space is limited, so please register in advance to reserve your place. We hope to see you there!
http://www.nd.edu/~ccl/workshop/2013
The workshop is an opportunity for beginners and experts alike to learn about the latest software release, get to know the CCL team, meet other people engaged in large scale scientific computing, and influence the direction of our research and development.
Thursday, October 10th
Afternoon: Introduction and Software Tutorials
Friday, October 11th
All Day: New Technology, Scientific Talks, and Discussion
There is no registration fee, however, space is limited, so please register in advance to reserve your place. We hope to see you there!
Wednesday, August 21, 2013
New Work Queue Paper at IEEE Cluster 2013
Michael Albrecht and Dinesh Rajan will present their latest work titled Making Work Queue Cluster Friendly for Data Intensive Scientific Applications.
In the original design of Work Queue, each worker was a sequential process that executed one task at a time. This paper describes the extension of Work Queue into two respects:
The effect of these two changes is to dramatically reduce the network footprint at the master process, and at each execution site. The resulting system is more 'friendly' to local clusters, and is capable of scaling to even greater sizes.
In the original design of Work Queue, each worker was a sequential process that executed one task at a time. This paper describes the extension of Work Queue into two respects:
- Workers can now run multiple tasks simultaneously, each sharing a local cache directory.
- Workers can be combined into hierarchies, each headed by a foreman, which provides a common disk cache for each sub tree.
The effect of these two changes is to dramatically reduce the network footprint at the master process, and at each execution site. The resulting system is more 'friendly' to local clusters, and is capable of scaling to even greater sizes.
Monday, July 29, 2013
CCTools 4.0 Released
The Cooperative Computing Lab is pleased to announce the release of version 4.0 of the Cooperative Computing Tools, including Parrot, Chirp, Makeflow, WorkQueue, SAND, All-Pairs, and other software.
This is the first release of the 4.0 series, with some major changes:
Please refer to the doc/ directory in the distribution for the usage of this new features. You can download the software here:
Download
Thanks goes to the contributors for this release: Michael Albrecht, DeVonte Applewhite, Peter Bui, Patrick Donnelly, Brenden Kokoszka, Kyle Mulholland, Francesco Prelz, Dinesh Rajan, Casey Robinson, Peter Sempolinski, Douglas Thain, Ben Tovar, and Li Yu.
This is the first release of the 4.0 series, with some major changes:
- To support new features on WorkQueue, backwards compatibility of master and workers pre-4.0 is broken. Specifically, workers from 4.0 cannot connect to masters pre-4.0, and masters from 4.0 will not accept connection from workers pre-4.0. The API did not change, thus unless you want to take advantage of new features, you should not need to modify your code.
- All code related to WorkQueue has been consolidated to its own library. When linking work queue applications in C, you will need to use: -lwork_queue -ldttools rather than just -ldttools. If you are using the perl or python bindings, no change is necessary.
- The auto-mode option -a for communicating with the catalog server is being deprecated. It is now implied when a master, or project name (-M, -N) is specified.
- Most tools now support long options at the command line (e.g., --help).
- [WorkQueue] Support for workers hierarchies, with a master-foremen-workers paradigm. [Michael Albrecht]
- [WorkQueue] Multi-slot workers. A worker now is able to handle more than one task at a time. [Michael Albrecht]
- [WorkQueue] Resource reports. A worker reports its resources (disk, memory, and cpu) to the master, and each task in the master can specify a minimum of such resources. [Michael Albrecht, DeVonte Applewhite]
- [WorkQueue] Authentication between master and workers when using the catalog server [Douglas Thain].
- [WorkQueue] Python bindings now include most C API. [Dinesh Rajan]
- [WorkQueue] Several bug fixes and code reorganization. [Dinesh Rajan, Michael Albrecht]
- [WorkQueue] Policies can be specified to work_queue_pool to submit workers on demand. [Li Yu] [Makeflow] Support for task categories. A rule can be labeled with a category, and required computational resources (disk, memory, and cpu) can be specified per category. Makeflow then automatically communicates these requirements to work queue or condor. [Ben Tovar]
- [Parrot/Chirp] Support for a search system call added. Search allows for finding files in a number of directories with a shell pattern. See parrot_search for more information. [Patrick Donnelly, Brenden Kokoszka]
- [Parrot] Several bug fixes for cvmfs support. [Douglas Thain, Ben Tovar, Patrick Donnelly]
- [Monitor] A resource monitor/watchdog for computational resources (e.g. disk, memory, cpu, and io) that can be used standalone, or automatically by Makeflow and Work Queue. [Ben Tovar]
- [Monitor] A visualizer that builds a webpage to show the resources histograms from the reports of the resource monitor. [Casey Robinson]
Please refer to the doc/ directory in the distribution for the usage of this new features. You can download the software here:
Download
Thanks goes to the contributors for this release: Michael Albrecht, DeVonte Applewhite, Peter Bui, Patrick Donnelly, Brenden Kokoszka, Kyle Mulholland, Francesco Prelz, Dinesh Rajan, Casey Robinson, Peter Sempolinski, Douglas Thain, Ben Tovar, and Li Yu.
Friday, July 26, 2013
Ph.D. Defense: Li Yu
Congratulations to Dr. Li Yu, who successfully defended his Ph.D. dissertation, Right-sizing Resource Allocations for Scientific Applications in Clusters, Grids, and Clouds!
Monday, July 22, 2013
Tutorial on Building Scalable Scientific Applications at XSEDE13
We will be offering a tutorial titled Building Scalable Scientific Applications using Makeflow and Work Queue as part of XSEDE 2013 in San Diego on July 22.
Subscribe to:
Posts (Atom)

