Resource Allocation in Massively Heterogeneous Computer Systems: A Distributed Approval
Abstract
Future computing architectures promise an unprecedented degree of heterogeneity in their capabilities and connectivity. At the same time, the jobs performed on such architectures are themselves becoming more heterogeneous: as increasing amounts of different types of data are collected, there is a corresponding increase in the analysis and processing that can be done on this data. UAVs (unmanned aerial vehicles), for instance, can now collect enormous amounts of visual data and use it for computational jobs ranging from target identification to three-dimensional terrain visualization. These jobs, in turn, can then be run on one or more types of computational resources, from localized processing on the UAVs themselves to processing on cloud servers that may have a wide variety of available compute and memory resources. These two complementary increases in heterogeneity have created a need for new computing architectures to "match" the best set of computational resources to a set of user jobs. Yet centralized matching algorithms are unlikely to scale to the massive degree of heterogeneity and amount of data that characterize future computing needs. In highly dynamic scenarios like battlefield operations, they also may not be able to adapt to changing user needs or resource availability. The proposed work will investigate an 11ltemative, incentives-based approach that is inherently scalable, dynamic, and flexible to heterogeneity in compute resources and jobs. We consider multiple users that wish to run several, possibly inter-dependent computational jobs at multiple compute providers. Our approach is based on the fundamental insight that providers have the best knowledge of their capabilities and users have the best knowledge of their job requirements. Thus, a natural choice for a distributed matching algorithm would be to have users choose the resource(s) on which to run their computations. Yet these choices cannot be made independently: compute providers will have performance constraints, meaning that users must compete for resources at each provider and should coordinate their actions in order to achieve good overall system performance Even if user coordination can be achieved, defining the "best" allocation of resources to jobs may involve tradeoffs between different performance metrics: the most efficient or cost-effective use of resources, for instance, may not accurately reflect the priorities of different user jobs. We propose to enable user coordination by having compute providers "charge" users virtual prices for their resource consumption. Users will then need to decide whether to pay more for more "valuable" resources, and conversely compute resource providers will need to decide how much to charge users. These virtual prices function as easily interpretable signals of resource availability and user needs and priorities. The major anticipated results of the project will be (1) analytical results comparing the effectiveness of a distributed pricing approach to a centralized one, (2) a software suite that allows users and providers to utilize virtual pricing in order to allocate heterogeneous resources to heterogeneous jobs, and (3) a testbed demonstration of the software suite for Army-relevant information processing applications.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1910036
Entities
People
- Carlee Joe-Wong
Organizations
- Army Contracting Command
- Massachusetts Institute of Technology
- United States Army