Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 1Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.1EE244: Design Technology for Integrated Circuits and SystemsOutlineLecture 7.1◆ Regular Module Structures▲ General Array generation◆ Introduction to Behavioral Synthesis▲ Relationship to silicon compilationEE244 Fall 97 7.1.2What is High-Level Synthesis?◆ Many terms have been used:▲ Algorithmic, Functional, Behavioral, Architectural, ...◆ "High Level Synthesis means going from analgorithmic level specification of the behavior of adigital system to a register-level structure thatimplements that behavior."» McFarland, et. al., Proc. IEEE, February 1990.▲ Input specification: gives required mappings fromsequences of inputs to sequences of outputs.▲ Must satisfy constraints: cycle-time, area, power, etc.Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 2Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.3Algorithms and Programs◆ Algorithm: specifies a sequence of steps whichmust be carried out in order to solve a problem▲ Algorithm = Control-flow Program▲ (Parallel Algorithm = Parallel Control-flow Program)◆ Program: specifies a set of operations (essentiallyunordered) which must be carried out (in anappropriate order, if need be) on a set of input datain order to produce a desired set of output data.▲ Needed order is a partial order defined by:▼Data dependencies▼Temporal dependencies (if sequential).EE244 Fall 97 7.1.4for(i=0 to 9) {x[i]=y[i]+c; /* "forall" */}j=0;while(j < 10) {x[j]=y[j]+c;j=j+1;}Sequential Control-Flow Model◆ Based on Von Neumann "fetch;execute;store" with single (serialcontrol flow) or synchronized multiple (parallel control flow) thread(s)of control.◆ Proposes an ordering of computation based on strict, temporalsequencing of operations, in line with above cycle.◆ Not well suited to the description of hardware since arbitraryhardware rarely fits such a model of computation.◆ Ability to combine several operations and treat them as a unit, orblock (begin-end, parbegin-parend, ...)◆ Ability to allow an operation to be executed in a loop.e.g. ISP, DDL/P(1973), Adlib/Sable(1980), AHPL(1973) SLANG(1982).Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 3Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.5What is High-Level Synthesis?◆ "... the system to be designed is usuallyrepresented at the algorithmic level by aprogramming language like Pascal or Ada, or by anHDL that is similar to a programming language...."(e.g. ISPS, DSL, MIMOLA, VHDL Behavior)◆ "...most high-level synthesis systems useprocedural languages... "» McFarland, et. al., Proc. IEEE, February 1990.EE244 Fall 97 7.1.6Behavioral Descriptionor SpecificationImplementationModelHigh-Level Designor SynthesisVHDL BehavioralDescriptionVon Neumann-styleControl & DatapathSignal Flow GraphSystolicArrayWhat is High-Level Synthesis?Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 4Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.7The transactional (system) levelThe behavioral (architectural) levelThe register levelThe sequential levelThe combinational levelRepresenting the Synthesis Problem:The Conventional ApproachEE244 Fall 97 7.1.8Apply the "Microscope Test" to the DesignCombinational BehaviorStoreRepresenting the Synthesis Problem:An Alternative ApproachImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 5Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.9What is an Architecture?◆ Amdahl, Blaauw, and Brooks, 1964, definedthree interfaces:▲ Computer Architecture: "The attributes of acomputer as seen by a machine languageprogrammer."▲ Implementation: "Actual hardware structure,logic design, and datapath organization."▲ Realization: "Encompasses the logictechnologies, packaging, and interconnection."EE244 Fall 97 7.1.10What is an Architecture?◆ A description of the behavior of a system that isindependent of its implementation.▲ Isomorphic to its "interface specification" (Siewiorek, Bell,Newell, 1971)▲ For example:▼Instruction set definition of a computer▼Z-domain description of a filter▼ Handshaking protocol for a bus◆ May guide implementation (contain ’hints’ or’pragmas’)▲ e.g. a particular specification may lead naturally to a serialor parallel implementation.Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 6Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.11Example: Instruction setInst_A Inst_B Inst_C ... Inst_C may not follow Inst_AArchitectureInst_A Inst_B Inst_C ... Inst_C may not follow Inst_A because Inst_A uses a scratchpad register that Inst_C will over-write.Not architectureWhat is an Architecture?EE244 Fall 97 7.1.12Specification vs. Description◆ Specification: Saying what I want; describes behaviorin terms of results.▲ e.g. ∀A { A[i,j] ← 0}◆ Description: Saying how to do it; describes behavior interms of procedure or process.e.g. for(i=0; i<N; i++)for(j=0; j<M; j++)A[i][j] = 0;◆ We do not have specification languages for general-purpose digital design. For some special-purposeapplications (e.g. DSP) we do.Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 7Copyright © 1997, A. Richard NewtonEE244 Fall 97 7.1.13High-Level Synthesis◆ How does one measure the quality of a solution?▲ Number of control steps (clock cycles in synchronoussingle-clock implementations)▼Chaining and overlapped operations.▲ Number of hardware functional units (e.g. ALU, adder,multipliers)▼Combinational or pipelined▲ Number of registers▲ Number of MUX inputs▲ Total connections and "unique connections."EE244 Fall 97 7.1.14Converting Procedural Descriptionsto a Dataflow-Oriented Representation◆ Determine scope of variables and apply single-assignment inthe scope◆ Convert Complex data-structures into simple types◆ Unroll loops with constant loop-counts (if appropriate)◆ Perform simple syntactic optimizations:▲ Move operations out of loops where possible▲ Simplify complex expressions▲ Extract common sub-expressionse.g. CMUDA:Value-trace (VT)HAL:CDFG,
View Full Document