CPU Torrent -- CPU Cycle Offloading to Reduce User Wait Time and Provider Resource Requirements

Swapneel Sheth, Gail E. KaiserColumbia 2008 · DOI

TL;DR

This paper introduces "CPU Torrent," a middleware system that offloads computationally intensive "utility" sub-jobs from scientific computing systems to external providers. This approach significantly reduces user wait times and the resource burden on the primary provider, especially for sequential or pipelined workflows that are difficult to parallelize locally.

What Problem Does This Paper Address?

Many scientific computing systems, particularly in fields like bioinformatics and computer animation, involve complex, sequential workflows. These systems often face significant user demand that outstrips their local computational resources, leading to long wait queues that can span days. While distributed computing and grid computing offer solutions for highly parallelizable tasks, they are less effective for inherently sequential computations or pipelined workflows where one step depends on the output of the previous one. Furthermore, some components of these workflows might be proprietary or require massive datasets, making it impractical to distribute them to every user's local machine. The challenge is to efficiently handle these sequential workflows when local resources are limited, without requiring users to download and manage large, complex software packages.

Methods

The core innovation is the "CPU Torrent" middleware. This system acts as an intermediary between a "proprietary service provider" (the main system) and "utility providers" (external services). The proprietary system is modified to identify and split off "utility" sub-jobs (e.g., sequence alignment like BLAST) from its main "proprietary" workflow. These utility sub-jobs are then sent to the CPU Torrent middleware.

CPU Torrent manages the offloading process through several components:

  • Middleware API: Allows proprietary providers to submit utility jobs and query their status.
  • Registry: Keeps track of available local and external utility providers and their services.
  • Queue Manager: Handles the queuing of utility jobs.
  • Queue Processor: Selects the best utility provider for a given sub-job.
  • Policy Manager: Determines the distribution ratios for sending sub-jobs to different providers based on a configuration file.
  • Service Wrappers: These are plug-ins that handle the specific invocation mechanisms and result retrieval for each utility provider.

The system is designed to be fault-tolerant, handling cases where utility providers are unavailable or return corrupted results by falling back to local execution.

Datasets

Not discussed in the paper. The paper focuses on a real-world bioinformatics system, PredictProtein, and its use of the BLAST algorithm as a utility sub-job.

Key Insights and Ideas

  • Decoupling Utility from Proprietary: The key insight is that many scientific workflows can be decomposed into "utility" components (widely available, often standardized) and "proprietary" components (unique, core functionality). Offloading the former can significantly alleviate the burden on the latter.
  • Leveraging Existing Infrastructure: CPU Torrent doesn't require users to set up their own compute clusters or download massive datasets. Instead, it leverages existing, publicly available utility services, making it practical for providers with limited resources.
  • Handling Sequential Workflows: Unlike traditional parallel computing approaches, CPU Torrent is designed for sequential or pipelined workflows. It uses the waiting time in the proprietary system's queue to offload the utility part, effectively overlapping computation.
  • Analogy to BitTorrent (with caveats): The name "CPU Torrent" draws an analogy to BitTorrent's decentralized file sharing. However, the authors acknowledge the analogy is weak, as CPU Torrent relies on pre-existing service providers rather than ad-hoc client contributions and doesn't involve the same dynamic peer discovery.

Key Results

The paper presents a theoretical analysis using Queuing Theory to demonstrate the potential benefits.

  • Reduced Wait Time: The primary benefit is a significant reduction in user wait time, especially during periods of high demand. The paper illustrates this with a plot showing processing time improvement as a function of the offloadable fraction of the job and the actual processing time.
  • Reduced Provider Load: CPU Torrent can reduce the CPU load on the proprietary service provider, freeing up local resources for other tasks or allowing the system to handle more jobs overall. Figure 7 shows a "Load Improvement" plot, indicating that even with zero queue wait time, offloading can reduce local server load.
  • Proof-of-Concept Implementation: A proof-of-concept framework was implemented and tested with Columbia's PredictProtein system, demonstrating the feasibility of the approach.

Limitations and Future Work

  • Analogy Weakness: The authors admit the analogy to BitTorrent is weak, as CPU Torrent relies on established service providers and doesn't involve dynamic peer joining/leaving.
  • Dynamic Load Balancing: Currently, provider selection is based on static configuration. Future work includes developing dynamic load balancing to automatically select providers with smaller wait times or job queues. This might involve programmatic monitoring or even "screen scraping" if direct monitoring isn't available.
  • Real-world Benefit Analysis: While theoretical analysis is provided, the paper mentions that the technology has been transferred to PredictProtein developers, and they await final integration to measure real-life benefits and compare them to theoretical predictions.
  • Community Building: Future work could involve organizing communities of users and providers, potentially using a "Karma Rating" based on historical contribution of quality service.
  • Offloading Intermediate/Suffix Jobs: The current focus is on offloading prefix sub-jobs, but the authors suggest that offloading intermediate and suffix sub-jobs would also reduce wait times and resource requirements.

Summary updated

Abstract

Developers of novel scientific computing systems are often eager to make their algorithms and databases available for community use, but their own computational resources may be inadequate to fulfill external user demand -- yet the system's footprint is far too large for prospective user organizations to download and run locally. Some heavyweight systems have become part of designated "centers" providing remote access to supercomputers and/or clusters supported by substantial government funding; others use virtual supercomputers dispersed across grids formed by massive numbers of volunteer Internet-connected computers. But public funds are limited and not all systems are amenable to huge-scale divisibility into independent computation units. We have identified a class of scientific computing systems where "utility" sub-jobs can be offloaded to any of several alternative providers thereby freeing up local cycles for the main proprietary jobs, implemented a proof-of-concept framework enabling such deployments, and analyzed its expected throughput and response-time impact on a real-world bioinformatics system (Columbia's PredictProtein) whose present users endure long wait queues.
BibTeX
@inproceedings{sheth2008cpu,
  author = {Swapneel Sheth and Gail E. Kaiser},
  title = {{CPU Torrent -- CPU Cycle Offloading to Reduce User Wait Time and Provider Resource Requirements}},
  booktitle = {Columbia},
  year = {2008},
  doi = {10.7916/d8gb2bxt},
}
Figure