Greedy Heuristics for Resource Allocation in Dynamic Distributed Real-Time Heterogeneous Computing Systems

Recently, with the widespread use of increasingly powerful commercial off-the-shelf (COTS) products, some real-time distributed system designers have started a shift from custom-made systems to COTS-based systems to get lower costs and more flexible systems. This research investigates the problem of allocating real-time applications to a set of COTS heterogeneous machines connected together by a COTS high-speed network. For the intended distributed real-time system, the work presented in this paper includes characterizing and modeling the applications and the hardware platform, identifying and quantifying the performance goal, and designing and developing heuristics for allocating the applications so as to optimize the performance goal. Each application has certain quality of service (QoS) constraints that must not be violated (i.e., constraints on the end-to-end latency and throughput). Unlike most of the related work in real-time systems, the focus of this work is on finding an initial static allocation of the applications onto the machines to maximize the allowable increase in workload until a dynamic reallocation of resources is required to avoid a QoS violation. This paper presents and compares three greedy heuristics to solve the initial mapping problem