High Level Synthesis System : RODIN 

ABSTRACT 

We developed High Level Synthesis System which synthesizes a Register 
Transfer (RT) level circuit from an LSI behavior specification described in 
the Pascal language. We prove that the parallel Simulated Annealing with 
heuristic knowledge can offer speed-up in solving Combinatorial Optimization 
Problems. 

Key Features 

Rule-based Annealing(RA) 

RA generates the new configuration not only at random but also through 
heuristic knowledge (rules). By letting rule selection ratios change dynami-
cally according to the cost reduction ratio of each rule, a better solution is 
produced at the appointed optimization time. 

Parallel formulation of RA 

PEs are clustered based on acceptance ratios. PEs in one cluster opti-
mize one configuration co-operatively and let the acceptance ratio increase at 
medium and low temperatures. 



System Configuration 

- 39 -

ABSTRACT 

An LSI is designed using a combination of register transfer level descrip-
tion,gate level description and behavior description. The logic synthesis and 
the layout-wiring have been largely automated. However,even now,high level 
synthesis is not available.Our study has focused on high level synthesis. 

HIGH LEVEL SYNTHESIS 

¥ Behavior description is parsed and developed to Binomials. 
¥ Initial schedule table is generated from Binomials. This is a data form 
  that corresponds to one datapath circuit and is possible to optimize. 
¥ Optimum schedule table is generated by Parallel RA optimizing. 
¥ Variables are allocated to registers based on the lifetime of the variables. 
¥ RT level description is generated in the Hardware Description Language. 
  It expresses both datapath and micro instruction code. 




- 40 -

RULE-BASED ANNEALING (RA) 

Heuristic knowledge (rules) are added to traditional Simulated Annealing 
(SA) to generate a new configuration for a schedule table. Each rule is applied 
probabilistically according to its selection ratio. Selection ratios of rules are 
dynamically updated so that greedy rules are used more often when the ap- 
pointed design time is short and random rearrangements are used more often 
when there is ample time. This method produces a better solution within the 
appointed time. 

OUTLINE OF DEMONSTRATION (1) 

(1) A Schedule table is a two-dimensional grid where each vertical slice 
    corresponds to a processing unit/ALU and each horizontal slice corre- 
    sponds to a time slot. Binomials (colored according to operation) are 
    placed in grid locations. 
 
(2) Annealing temperature T and acceptance ratio e~ T in the case that 
    AC (increase in cost) is 100. 

(3) Total cost and each part of the total cost correspond to a schedule ta- 
    ble 

(4) Total selection ratio of rules is classified by roles (to rearrange ran-
    domly, to decrease ALU cost, and to decrease Time cost). 






Demonstration (1) 

- 41 -

PARALLEL FORMULATION OF RA 

¥ Parallel RA can update schedule tables more times than SA at medium 
  and low temperatures. 
¥ A host PE controls all clusters, and each cluster consists of one master 
  PE and several slave PEs. 

  In each cluster, a master PE updates its own schedule table by using 
     the rearrangement procedures which slave PEs find in parallel. 

  A host PE increases the number of slave PEs by merging two clusters 
     gradually to avoid decreases in the acceptance ratio (update ratio). 

OUTLINE OF DEMONSTRATION (2) 

(1) Changes of cluster 
    First, all PEs except the host PE perform annealing processes as the 
    master PE. Then, some of the master PEs become slave PEs. 

(2) Changes in acceptance ratio 
    The black line shows parallel RA and the purple line shows serial SA. 

(3) Changes in cost 
    The black line shows parallel RA and the purple line shows serial SA. 





Demonstration (2) 
- 42 -