Fast Schedulability Analysis Using Commodity Graphics Hardware
Jimin Feng, Samarjit Chakraborty, Bertil Schmidt, Weiguo Liu, Unmesh Dutta Bordoloi · 2007
In this paper we explore the possibility of using commodity graphics processing units (GPUs) to speedup standard schedulability analysis algorithms. Our long-term goal is to exploit GPUs to accelerate common electronic design automation algorithms, most of which tend to be computationally expensive. Our main contribution in this paper is a reformulation of a standard demand bound criteria-based schedulability analysis algorithm as a streaming algorithm expressed in terms of computer graphics primitives. This allows the algorithm to be efficiently implemented on a GPU, thereby resulting in very attractive speedups.