Research On Multi-Dimensional Computing Model And Its Application In High-Level Synthesis Of Digital Systems

Recent years have seen the rapid growth of all kinds of digital systems, in all kindsof areas. Being pushed by the great market demand, the growth rate of digital systemswill remain at a high level. To design, test and manufacture digital systems with largerscale and higher complexity, we have to solve some new problems. One of the problemsis that digital systems with larger scale and higher complexity require more time todesign and test, however, the rapidly changing market demands a shorterTime-to-Market (TTM). Another problem is digital systems with larger scale and highercomplexity generally require more space and more power; however, what the marketneeds is digital systems with smaller size, less power consumption, and betterperformance. To address these problems, the designers have to improve designmethodology and create more advanced technologies. What's more, the relationshipbetween cost and performance must be respected and reasonable trade-off must be madeduring the whole process. Currently Single Dimentional Computing Model (SDCM) isused in description of digital systems, and only behaviors and results are considered inthe description. Since computation cost is not included in it, relationship between costand performance is not regarded, which makes cost optimization and trade-off hard torealize. By extending SDCM to Multi-Dimensional Computing Model (MDCM),integrating cost information into digital system description and making full use of thesecost information in high-level synthesis, we can naturally describe the relationshipbetween performance and cost, and bring new design methodology to digital systemdesign.In this paper, three aspects were studied on the basis of a new computing model-MDCM, which were properties and representation of MDCM, profiling and high-levelcost estimation based on MDCM and cost-aware high-level synthesis. Main researchwork and conclusions are as follows:(1) Extend SDCM to MDCM. Based on analysis of existing single-dimensionalcomputing model (SDCM) which is used in mathematics and general computinglanguages, a new computing model MDCM was proposed. Descriptions based onSDCM care only behavior and results of the object, however, its realization detail andrelated cost are ignored. However, cost is one of the most important aspects whenimaplementing a system, which may even determine its computability. MDCM extendsSDCM by allowing any number and type of properties in operands and operators. Thecost of operation is calculated through properties and calculation rules of operators and maintained in operands. It can be used for cost analysis and optimization in concreteimplementation of abstract computation problems. The new computing model wasapplied to an example application and results showed that it can clearly describe therelation between its behavior and cost, which made evaluation and optimization of costeasier.(2) Propose a new MDCM-based cost profiling method. Digital systems areessentially concrete implementations of computing systems so MDCM can be used indigital system design. High level description of digital systems generally hides muchinformation for abstraction purpose, including cost information. When synthesizing thedescription, only best effort methods are available. In this paper, a MDCM based costprofiling method was proposed. Through profiling on the MDCM description, relatedparameters can be gathered, and cost information can be deduced from them at highlevel, thus cost aware high-level synthesis can be realized. The description languageused in this paper is SystemC and power consumption of datapath is taken as anexample, however, the method can be easily extended to other description languagesand other cost aspects.(3) Propose a cost-aware high-level synthesis algorithm which exploitsmulti-dimensional information in the description. Cost information gathered throughprofiling or other analysis methods can be used for cost aware high-level synthesis andmulti-objective optimization and trade-off among different cost aspects can be achieved.A graph decomposition and combination based scheduling, allocation and bindingalgorithm—MOOS was proposed in this paper, which did high-level synthesis formulti-objective optimization. The typical resource-constrained scheduling problem wasfirstly addressed. The DFG of the problem was divided into several independent parts,each part was scheduled independently and then partial scheduling results werecombined gradually into complete solutions under the constraint of time upper boundsof each part. Unavailable nodes identification and fast minimum combination lengthprediction were used to speed up partial scheduling chain combination. Multi-objectiveoptimization can be achieved by integrating allocation and binding operation intoscheduling. Component binding information was attached to intermediate schedulingresults. During scheduling infeasible binding configurations were removed according touser specified cost constraints, and multi-objective optimization was achieved byutilizing user specified cost function. Allocation and binding of scheduling chains weremodeled as a weighted bipartite matching problem and solved using HungarianAlgorithm. Experiment results show that MOOS can find good results according todifferent cost constraints and it runs much faster than Integer Linear Programming (ILP)method. Research work done in this paper was mainly focused on cost optimization of highlevel large scale digital system design. Methods of digging and maintaining costinformation from high-level description and utilizing it in high-level synthesis wereproposed. MDCM was the basis of work in this paper, and utilization of which was notlimited to digital system, design: it can be used in cost analysis and optimization ofconcrete implementation of any computing problems.