Probabilistic Pipelines:
Pipelines are commonly used to achieve high performance by overlapping computations of stages, so tasks (or called nodes) in different stages can be executed in parallel. In the design of application-specific heterogenous pipelines, designers face two critical problems: the buffer placement problem (i.e., where to place buffers) and the functional assignment problem (i.e., what type of functional unit to execute each node). Due to uncertainties within the execution time of nodes, these problems become much more challenging.
The same nodes in a pipeline may not have fixed execution time due to the following reasons: conditional instructions, ambient temperature, different memory types, etc. The worst-case scenario is widely used to conduct high-level synthesis, in which the overly pessimistic worst-case execution time analysis is employed. In this paper, we study the synthesis of a system in the probabilistic scenario where the execution time is modeled as a random variable. Solutions obtained in the probabilistic scenario can be used for hard real-time systems as well as soft real-time systems with guaranteed confidence probability.
In various fields, such as multimedia, computer vision and control, pipeline is increasingly popular. A pipeline is composed of stages. Each stage contains all tasks between two consecutive buffers. Its latency is the summation of the execution times of all tasks in it. The throughput of a pipeline is the reciprocal of the maximum latency of all pipeline stages. In the probabilistic scenario, both latencies of stages and the throughput are random variables. It brings difficulties in placing buffers in the system. In particular, designers should decide how and where to optimally place buffers, such that the buffer cost (numbers) can be minimized while satisfying timing constraints with a guaranteed confidence probability.
Due to the heterogeneity in architectures, a task can be executed by multiple choices of functional units with different execution times and costs. The heterogeneity exponentially expands the design space but provides opportunities to eliminate the costs of unnecessary features. Hence, a critical and difficult problem arises: how to efficiently assign each task to the proper functional unit such that the functional cost can be minimized while satisfying timing constraints with a guaranteed confidence probability.
In this project, our objective is to find the global optimal solution of functional assignment and buffer placement in the probabilistic scenario, such that the total cost (including functional cost and buffer cost) of the resultant pipeline is minimized while satisfying the required throughput under a required confidence probability. When the required confidence probability is 100%, the obtained solution can be used for hard real-time systems. When the required confidence probability is less than 100%, the resultant pipelines can be applied to soft real-time systems to reduce total cost.
The newest results on this project are presented in the TETC paper.
Fix-Time Pipeline:
In high-level synthesis for special-purpose architectures of real-time embedded systems, it becomes critical to design a system with the minimum cost while satisfying performance requirements, where cost may relate to price, area, energy, lifetime, etc. In many systems, such as Digital Signal Processing (DSP) systems, the same type of operations can be processed by heterogeneous functional units with different costs (e.g., the addition operation can be performed by different types of adders). Therefore, an important problem arises: how to assign a proper functional-unit type to each operation of a given application such that the total cost can be minimized while the timing constraint can be satisfied.
There are two critical problems remained to be solved: (1) how to find optimal solution for applications with complicated structures, such as Directed Acyclic Graph (DAG) or cyclic Data Flow Graph (cyclic DFG), (2) how to guarantee the reliability of the resultant systems. This project targets on solving the above two problems.
The newest results on this project are presented in the TPDS paper.
Weiwen Jiang
Hailiang Dong (M.S. @ CQU)
Lei Yang (Ph.D. candidate @ CQU and UCI)
(acceptance rate 75/258=29.1%)
also appear at IEEE Transactions on Emerging Topics in Computing (TETC), Jan. 2018.
(acceptance rate 13/51=25.5%)
(acceptance rate 21/80=26.3%)
