PARLGRAN: parallelism granularity selection for scheduling task chains on dynamically reconfigurable architectures

• Main Authors: Banerjee, Sudarshan, Bozorgzadeh, Elaheh, Dutt, Nikil
• Format: Conference Proceeding
• Language: English
• Subjects: Computing methodologies > Artificial intelligence > Search methodologies > Heuristic function construction; Hardware > Electronic design automation > Physical design (EDA) > Placement; Hardware > Electronic design automation > Physical design (EDA) > Wire routing; Hardware > Hardware validation; Hardware > Very large scale integration design > Application-specific VLSI designs; Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis > Scheduling algorithms; Theory of computation > Design and analysis of algorithms > Online algorithms > Online learning algorithms > Scheduling algorithms; Theory of computation > Models of computation > Concurrency; Theory of computation > Models of computation > Concurrency > Parallel computing models; Theory of computation > Theory and algorithms for application domains > Machine learning theory > Reinforcement learning > Sequential decision making
• DOI: 10.1145/1118299.1118419

Partial dynamic reconfiguration, often called RTR (run-time reconfiguration) is a key feature in modern reconfigurable platforms. While partial RTR enables additional application performance, it imposes physical constraints necessitating simultaneous scheduling and placement while mapping application task graphs onto such architectures. In this paper we present PARLGRAN, an approach that maximizes performance of application task chains by selecting a suitable granularity of data-parallelism for individual data parallel tasks. Our approach focusses on reconfiguration delay overhead and placement-related issues (such as fragmentation) while selecting individual data-parallelism granularity as an integral part of simultaneous scheduling and placement. We demonstrate that our heuristic generates high-quality schedules on an extensive set of over a 1000 synthetic experiments by comparing the results with an approach that tries to statically maximize data-parallelism, i.e., does not consider the overheads and constraints associated with partial RTR. A detailed case-study on JPEG encoding additionally confirms that blindly maximizing data-parallelism can result in schedules even worse than that generated by a simple (but RTR-aware) approach oblivious to data-parallelism.