Introduction

The Trellis Project is investigating techniques to create a single metacomputer from a collection of high-performance systems. This includes work in scheduling, remote data access, distributed file systems, security, and a Web-based portal to metacomputers. Different user-level overlay metacomputers can be created using the same constituent systems on a (if desired) per-user basis.

The Principal Investigator is Paul Lu. The current graduate students are Mike Closson, Cam Macdonell, Paul Nalos, and Yang Wang. The project has benefited greatly from the significant contributions of Chris Pinchak, Jonathan Schaeffer, Meng Ding, Mark Goldenberg, Nicholas Lamb, George Ma, Danny Ngo, Victor Salamon, Mark Lee, Morgan Kan, Nolan Bard, and others. We gratefully acknowledge research support from C3.ca, Alberta's Ministry of Innovation and Science, NSERC, CFI, and SGI.

From September 15 to September 17, 2004, the CISS-3 Experiment (the Third Canadian Internetworked Scientific Supercomputer) used the latest Trellis technology to harness over 4,000 processors from across Canada into a virtual supercomputer or metacomputer. With a ramp up and ramp down, the actual number of concurrent jobs varied over the 48 hour period of the experiment, but we had 4,000+ jobs running, at the peak. Two applications, one studying protein folding using GROMACS and another studying biological membranes using CHARMM, were used. CISS-3 also marked the first production use of the Trellis File System (see below) in both library-based and NFS-based forms.

On November 4, 2002, the CISS Experiment (the Canadian Internetworked Scientific Supercomputer) used technology from the Trellis Project to harness over 1,300 processors from across Canada into a virtual supercomputer or metacomputer. The application was a MOLPRO-based computational chemistry problem from Dr. Wolfgang Jäger's group (Dept. of Chemistry, U. of Alberta).

Overview and Context

Put simply, a metacomputer is an useful aggregation of individual computer systems. We have developed techniques to schedule jobs and create file systems across computers that span different institutions and administrative domains. The advantage of the Trellis approach is a high level of functionality, simplicity, and minimal changes to the underlying software infrastructure.

In computing science, the dream of metacomputing has been around for decades. In various forms (and with important distinctions), it has also been known as “distributed computing”, “batch scheduling”, “cycle stealing”, and (most recently) “grid computing”. Some well-known, contemporary examples in this area include SETI@home, Project RC5/distributed.net, Condor, Legion, PUNCH, UNICORE, and the projects associated with Globus/Open Grid Service Architecture (OGSA). In Canada, Grid Canada has been exploring Globus technology since September 2001.

SETI@home, Project RC5, and similar projects are based on single applications (e.g., signal processing, cracking codes); Trellis is designed to support arbitrary applications. Currently, we do not use any of the new software that might be considered part of “grid computing”; Trellis is exploring alternate approaches to metacomputing. However, the design of Trellis allows us to incorporate and/or co-exist with grid technology, in the future, through the use of (say), grid-enabled Secure Shell.

Of course, there are many, many other related projects. Google the above terms or look on Slashdot. Some of the projects are cited in our academic papers, listed below.

Trellis NFS and Brief CISS-3 Results

CISS-1 and CISS-2 Overview and Results

Abstract: On November 4, 2002, a Canada-wide virtual supercomputer gave a chemistry research team the opportunity to do several years worth of computing in a single day. This experiment, called CISS-1 (Canadian Internetworked Scientific Supercomputer), had three research impacts: (1) in partnership with C3.ca, created a new precedent for cooperation among Canadian high-performance computing sites, (2) demonstrated the scalability and capabilities of the Trellis system for wide-area high-performance metacomputing, and (3) produced a new computational chemistry result.

Using roughly 1,376 dedicated processors, at 20 facilities, and in 18 administrative domains across the country, approximately 3.5 CPU years of computing were completed. CISS-1 is a prototype for future research projects requiring large-scale computing in Canada. This is the first step towards making CISS a regular event on the Canadian research landscape.

Trellis Security Infrastructure
(TSI)

Abstract: Researchers often have access to a variety of different high-performance computer (HPC) systems in different administrative domains, possibly across a wide-area network. Consequently, the security infrastructure becomes an important component of an overlay metacomputer: a user-level aggregation of HPC systems. The Grid Security Infrastructure (GSI) uses a sophisticated approach based on proxies and certification authorities. However, GSI requires a substantial amount of installation support and it requires human-negotiated organization-to-organization security agreements.

In contrast, the Trellis Security Infrastructure (TSI) is layered on top of the widely-deployed Secure Shell (SSH) and systems administrators only need to provide unprivileged accounts to the users. The contribution of the TSI approach is in demonstrating that a single sign-on (SSO) system can be implemented without requiring a new security infrastructure. We describe the design of the TSI and provide a tutorial of some of the tools created to make the TSI easier to use.

Placeholder Scheduling

Abstract: A practical problem faced by users of high-performance computers is: How can I automatically load balance my jobs across different batch queues, which are in different administrative domains, if there is no existing grid infrastructure? It is common to have user accounts for a number of individual high-performance systems (e.g., departmental, university, regional) that are administered by different groups. Without an administration-deployed grid infrastructure, one can still create a purely user-level aggregation of individual computing systems.

The Trellis Project is developing the techniques and tools to take advantage of a user-level overlay metacomputer. Because placeholder scheduling does not require superuser permissions to set up or configure, it is well-suited to overlay metacomputers. This paper contributes to the practical side of grid and metacomputing by empirically demonstrating that placeholder scheduling can work across different administrative domains, across different local schedulers (i.e., PBS and Sun Grid Engine), and across different programming models (i.e., Pthreads, MPI, and sequential). We also describe a new metaqueue system to manage jobs with explicit workflow dependencies.

Workflow and DAG Scheduling

Abstract: High-performance computing often involves sets of jobs or workloads that must be scheduled. If there are dependencies in the ordering of the jobs (e.g., pipelines or directed acyclic graphs) the user often has to carefully, manually submit the jobs in the right order and/or delay submitting dependent jobs until other jobs have finished. If the user can submit the entire workload with dependencies, then the scheduler has more information about future jobs in the workflow. We have designed and implemented TrellisDAG, a system that combines the use of placeholder scheduling and a subsystem for describing workflows to provide novel mechanisms for computing non-trivial workloads with inter-job dependencies. TrellisDAG also has a modular architecture for implementing different scheduling policies, which will be the topic of future work. Currently, TrellisDAG supports: (1) A spectrum of mechanisms for users to specify both simple and complicated workflows. (2) The ability to load balance across multiple administrative domains. (3) A convenient tool to monitor complicated workflows.

Trellis Driver

for interfacing
with Java;
using a
bioinformatics
case study

Abstract: Some applications in science and engineering consist of a main job that invokes, or drives, other jobs. For example, a server process may receive a request, then invoke a workflow of stand-alone scripts or executables to handle the request, and then generate the final response. Java's Runtime.exec() function allows jobs to be invoked from within a master Java program. However, these jobs are usually restricted to the same machine. If the number of jobs in the workflow is large, then it can be desirable to load balance the workload across different servers to maximize throughput.

We describe the design and implementation of the Trellis Driver, a newly-developed Java module that runs jobs using TrellisDriver.exec() and allows jobs to be scheduled across clusters and metacomputers (i.e., aggregations of servers). Using a Java-based bioinformatics application as a case study, we evaluate the performance improvement Trellis Driver offers through workflow parallelism.

Trellis-SDP

for simple
data parallel
applications

Abstract: Some datasets and computing environments are inherently distributed. For example, image data may be gathered and stored at different locations. Although data parallelism is a well-known computational model, there are few programming systems that are both easy to program (for simple applications) and can work across administrative domains.

We have designed and implemented a simple programming system, called Trellis-SDP, that facilitates the rapid development of data-intensive applications. Trellis-SDP is layered on top of the Trellis infrastructure, a software system for creating overlay metacomputers: user-level aggregations of computer systems. Trellis-SDP provides a master-worker programming framework where the worker components can run self-contained, new or existing binary applications. We describe two interface functions, namely trellis_scan() and trellis_gather(), and show how easy it is to get reasonable performance with simple data-parallel applications, such as Content Based Image Retrieval (CBIR) and Parallel Sorting by Regular Sampling (PSRS).

TrellisWeb Portal

(formerly PBSWeb)

Abstract: The resource managers (e.g., batch queue schedulers) used at many parallel and distributed computing centers can be complicated systems for the average user. A large number of command-line options, environment variables, and site-specific configuration parameters can be overwhelming. Therefore, we have developed a simple Web-based interface, called PBSWeb, to the Portable Batch System (PBS), which is our local resource manager system.

By using a Web browser and server software infrastructure, PBSWeb supports both local and remote users, maintains a history of past job parameters, and hides much of the complexities of the underlying scheduler. The architecture and implementation techniques used in PBSWeb can be applied to other resource managers.

Since our first description of the PBSWeb project, we have completely re-implemented the system to address three important deficiencies:

1. Instead of using the filesystem to manage job histories, we are now using the PostgreSQL relational DBMS to improve history queries and reliability.
2. Instead of clear text socket connections, we are using the Apache Web server with Secure Socket Layer to improve the security of communications between browser and server.
3. Instead of using Perl and raw HTML documents, we are using the PHP server-side scripting language to access the PostgreSQL database, to manage user sessions, and to create dynamic Web pages.

We describe the security and history management benefits of the new PBSWeb.