Architectural Synthesis for Applications with Imprecise Specifications

One of the most challenging problems in the area of system synthesis is to resolve uncertainties originated from initial imprecise specifications. Impreciseness in the architectural synthesis usually exists due to the lack of the exact knowledge about components which have not been completely designed down to the geometric level or due to manufacturing variances. The uncertainties of latency constraint, execution time, and power dissipation give automatic synthesis great challenges of obtaining a satisfactory design. These uncertainties in the specification and synthesis phases result in many time-consuming and expensive re-design cycles which may involve repeated re-specifications and re-syntheses.

Based on probability theory, two novel loop scheduling algorithms, probabilistic retiming (PR) and probabilistic rotation scheduling (PRS), are designed to statically schedule these tasks for non-resource and resource constrained systems respectively. These algorithms expose the parallelism of the probabilistic tasks across iterations. For a system without resource constraints, PR can be applied to optimize the input graph (i.e., reduce the cycle or clock period, $c$, of the graph such that the probability that the clock period is less than or equal to $c$ is greater than or equal to a given confidence probability $\theta$). The resulting graph implies a schedule for the non-resource constrained system. On the other hand, the PRS algorithm is used to schedule uncertain tasks to limited multiple functional units. It produces a schedule length from the given graph and incrementally reduces the length such that the probability of it being less than the previous length is greater than or equal to the given confidence probability. Consequently, by applying our algorithms, a good initial design solution can be obtained.

Based on the fuzzy theory, we also designed a polynomial-time scheduling algorithm which can efficiently construct schedules close to the ones obtained by exhaustive search. By considering the imprecise information, the chances of over/under estimation of system latency can be reduced. Experimental results shows the effectiveness and efficiency of our approach by comparing designs generated by our algorithm with the traditional scheduling scheme assuming worst case (or typical case) timing values, as well as exhaustive method.

Four journal papers and 7 conference papers were published under this category.