Algorithms and High-Level Models


For designs with significant control flow, algorithms can be described in software languages, flowcharts, abstract state machines, algorithmic state machines, etc.
For designs with trivial control flow (e.g. every parcel of input data undergoes the same computation), data-dependency graphs (section 2.4.2) are a good way to describe the algorithm.
For designs with a small amount of control flow (e.g. a microprocessor, where a single decision is made based upon the opcode) a set of data-dependency graphs is often a good choice.

When creating an algorithmic description of your hardware design, think about how you can represent parallelism in the algorithmic notation that you are using, and how you can exploit parallelism to improve the performance of your design.

Flow Charts and State Machines:
Flow charts and various flavours of state machines are covered well in many courses. Generally everything that you've learned about these forms of description are also applicable in hardware design. In addition, you can exploit parallelism in state machine design to create communicating finite state machines. A single complex state machine can be factored into multiple simple state machines that operate in parallel and communicate with each other.

In software, the expression: (((((a + b) + c) + d) + e) + f) takes the same amount of time to execute as: (a + b) + (c + d) + (e + f).
But, remember: hardware runs in parallel. In algorithmic descriptions, parentheses can guide parallel vs serial execution. In hardware, (((((a + b) + c) + d) + e) + f) takes 5 adders with a depth of 5 for result, and using (a + b) + (c + d) + (e + f) also takes 5 adders but just a depth of 3 to compute the result.
Datadependency graphs capture algorithms of datapath-centric designs. Datapath-centric designs have few, if any, control decisions: every parcel of input data undergoes the same computation.

High-Level Models:
There are many different types of high-level models, depending upon the purpose of the model and the characteristics of the design that the model describes. Some models may capture power consumption, others performance, others data functionality.

High-level models are used to estimate the most important design metrics very early in the design cycle. If power consumption is more important that performance, then you might write highlevel models that can predict the power consumption of different design choices, but which has no information about the number of clock cycles that a computation takes, or which predicts the latency inaccurately.

Conversely, if performance is important, you might write clock-cycle accurate high-level models that do not contain any information about power consumption. Conventionally, performance has been the primary design metric. Hence, high-level models that predict performance are more prevalent and more well understood than other types of high-level models. There are many research and entrepreneurial opportunities for people who can develop tools and/or languages for high-level models for estimating power, area, maximum clock speed, etc.

{ 1 Reactions ... read them below or add one }

Anonymous said on January 10, 2006 at 9:13 AM

Christmas is just around the corner. No time to go to the mall...then do your shopping online. We sell everything that the mall sells. Shop today!

Post a Comment

Your comments will be moderated before it can appear here.