Aggressive scaling in integrated circuits creates new challenges such as an increase in power density, temperature, and especially process variation in designing Multiprocessor Systems-on-Chip (MPSoC). While most of the previous works attempt to mitigate the process variation effects at the system level, the eventual design still suffers from the variability of frequency and leakage power. In this paper, we propose a method calledStereothat combinesstochastic and decomposition to solve task assignment and scheduling under process variation in MPSoCs. In our previous work, we formulated a Mixed Integer Linear Programming (MILP) problem for variation-aware task assignment and scheduling to optimize energy consumption while meeting the real-time constraints. To capture the stochastic behavior of process variation, we employed a chance-constrained programming technique to turn the problem into a corresponding stochastic optimization that can be solved by typical ILP solvers. However, it had a scalability problem. To address this issue, in this work, we leverage a Logic-based Benders Decomposition (LBD) approach to improve the running time for finding an optimal solution of assignments and schedulings under process variation phenomenon). We carried out extensive experiments using Embedded System Synthesis Benchmarks Suite (E3S). The experimental results of the Stereo method evince considerable improvements compared to the baseline method in terms of performance-yield and run-time. The Stereo-based MILP method ameliorates performance-yield up to 2× and run-time by 532×. Moreover, for manifold applications, the Stereo-based LBD method archives 3.47×-91.49× run-time improvement compared to the Stereo-based MILP approach and is capable of assigning and scheduling of more than 50 tasks on 9 processors.

Nowadays, aggressive scaling in integrated circuits brings out new challenges such as increase in power density, temperature, and process variation in designing Multiprocessor Systems-on-Chip (MPSoC) employed in embedded systems. While most of the previous works attempt to mitigate the process variation effects in system design level, the eventual design still is inefficient and suffers from the variability of frequency and leakage power of processors in a MPSoC. In this paper, we formulate a MILP problem for variation-aware task assignment and scheduling to optimize power consumption while meeting the real-time constraints. To capture stochastic behavior of process variation, we employ chance-constrained programming technique to turn the problem into a corresponding stochastic optimization one that can be solved by typical solvers. Extensive experiments using E3S benchmarks have been carried out and the obtained results of the proposed method evince improvements compared to the baseline method in terms of performance-yield and run-time.

Algorithmic skeletons are high-level representations for parallel programs that hide the underlying parallelism details from program specification. These skeletons are defined in terms of higher-order functions that can be composed to build larger programs. Many skeleton frameworks support efficient implementations for stand-alone skeletons such as map, reduce, and zip for both shared-memory systems and small clusters. However, in these frameworks, expressing complex skeletons that are constructed through composition of fundamental skeletons either requires complete reimplementation or suffers from limited scalability due to required global synchronization. In the STAPL Skeleton Framework, we represent skeletons as parametric data flow graphs and describe composition of skeletons by point-to-point dependencies of their data flow graph representations. As a result, we eliminate the need for reimplementation and global synchronizations in composed skeletons. In this work, we describe the process of translating skeleton-based programs to data flow graphs and define rules for skeleton composition. To show the expressivity and ease of use of our framework, we show skeleton-based representations of the NAS EP, IS, and FT benchmarks. To show reusability and applicability of our framework on real-world applications we show an N-Body application using the FMM (Fast Multipole Method) hierarchical algorithm. Our results show that expressivity can be achieved without loss of performance even in complex real-world applications.