In Designs: A HLS Perspective, Design requirements are presented and categorized based on High level Synthesis tool perspective. How those requirements are met, was not discussed in the article.

To meet the requirements outlined in Designs: A HLS Perspective, high level synthesis tools have to employ few techniques. These techniques may be employed in a manner that these  are transparent to designers or may create usability issues and add to learning curve.

For example, A command or extension need to be added to existing language like ANSI-C to determine the width of data path. Now it can be achieved in following different ways

• Method A: A 'special' type keyword added to ANSI C. Existing ANSI-C Code is modified for each data type.
• Method B: A 'special' type keyword added to ANSI C. Existing ANSI-C Code modification is required for only input & output data types. All other internal data types are automatically extracted.
• Method C: A constraint command is defined which can be added to ANSI C Code 'inline style' or can be specified in constraints file. All other internal data types are automatically extracted.

Method 'C' doesn't necessiate need of two separate files, one as golden reference and other as 'hardware' version and according to me, Method C is the best option. What do you think? Please vote.

{pollxtbot id=2}

{pollxtresultbot id=2}

Similar to data path synthesis, special timing constructs are needed to implement bus interface in ANSI C. Issue is that once these constructs are available, design style becomes like RTL coding style. Even if tool may not require usage of these constructs to implement algorithmic portion of application, designers will use it anyway. To force designer to think at higher level of abstraction, these option should not be part of language at all. This creates further sub catagory in High Level Synthesis tools, called Algorithm Synthesis tools. Such high level synthesis tool will not be able to handle interface/bus protocol effectively but is adept at handling algorithms. I think it is okay as long as bus protocols are standards driven.

In Ranking System, pure ANSI C gets highest mark and added constructs/limitations will cost. On other hand, pure ANSI C based tool will not be able to handle bus protocols. Reality is that no tool is going to achieve perfect score. But any tool with ease of use will win eventually and remember QoR is the key!

As mentioned in HLS Tools Benchmarking System, there is an effort is underway on SVTechie.com to develop a hypothetical High Level Synthesis Ranking System. 

High-level synthesis of digital systems from a behavioral description has received significant attention in the last 15years. However, commercial synthesis tools have gained limited acceptance among designers, primarily due to poorsynthesis results in the presence of conditionals and especially loops, and lack of controllability of quality of results.

To measure High Level Synthesis tool effectiveness, design requirements, as well as various performance parameters needs to be defined for High Level Synthesis tool. First, design expectations are presented below. Next, performance parameters will be defined and presented.

In simplistic view, High Level Synthesis tool should be able to handle full digital portion of SoC and with good QoR. But this simplistic expectation is flawed and is equivalent of expecting RTL/ASIC design methodology to handle analog designs. For proper characterization, Digital Design Requirements must be categorized as followed.

• Control Intensive Design

Control portion can be characterize by decision making block in the design. High level synthesis tools, generally have problem in generating high performance control circuit. This is because control-dominated circuits are very sensitive to clock cycles and this puts added pressure on scheduling algorithm in High Level Synthesis tools. Bus protocols are extreme form of control dominated circuit, where a part of logic has to communicate within a clock cycle. On other hand, FSMs (Control State Machines) are more flexible (in scheduling sense) compared to bus protocols. Any high level synthesis tool must be able to FSMs embedded in the designed. Bus Protocols handling is little tough and is categorized separately.

• Bus Protocols
  

As mentioned before, Bus Protocols are difficult to synthesize in High Level Synthesis domain because of scheduling sensitivity of design. Also, special constructs are needed to describe time sensitive handshake protocol effectively. However, addition of these construct in existing high level language results in added complexity, large learning ramp and programming issues.

• Data Path Intensive Design
  

This is relatively straight forward section of design from High Level Synthesis perspective. Though effective resource sharing is required to achieve good QoR. How variable types are specified and extracted, also impacts performance and may create usability issue. 

• Interface Synthesis
  

Interface serves as communication channel between two algorithmic sections in a design. It comprises of data path as well as some control signals to facilitate data transfer. Tools ability to automatically extract and generate appropriate interface may be good feature.

• External IP Interface

Tools should have proper interface to allow external IPs to be integrated into the design.

• Facilitate ECOs

Tools should be able to support/allow local changes in the design flow without requiring to go through the design flow.

I am trying to build an hypothetical system to benchmark various high level synthesis tools.

Recently, design community has started to warm up to the idea of High Level Synthesis tools again. However, there still exists a significant barrier to High Level Synthesis tool adoptation. See Analysis - Failure of High Level Synthesis Tools. Idea is to enable design community to make decision and set correct expectations in regards to High Level Synthesis tools.

Performance parameters for High Level Synthesis tool are defined and based on these parameters, a hypothetical benchmark system is created. Tool benchmark is done entirely based on public domain information to avoid copyright & intellectual property issues and to keep system unbiased. Needless to say, feedbacks are appreciated. Efforts are underway to develop a representative design problem to measure tool effectiveness as well.

Stay tuned for blog entries and articles!

Following paper makes case of Dependence Flow Graph and how it can be used to implement a transformation algorithm with example for constant propagation algorithm.  Actually, Dependence Flow Graph can be used in High Level Synthesis too to perform various optimizations and to calculate cost associated with various tradeoffs.

Paper has made an interesting observation (as an analogy) about Arabic-Hindu numeral representation. By using Arabic-Hindu system, it is much easier to perform  complex arithmatic operations as against Roman numeral system. How true!

Interesting read @ Dependence Flow Graph

In High Level Synthesis world, effectiveness of any tool depends on  its ability to extract parallelism, inherent in the application. Please read Limits of Instruction Level Parallelism for thorough discussion on parallelism related issues.

Degree of parallelism is directly dependent on Dependence in the code. Any high level synthesis tool should be able to understand, resolve and circumvent dependence to increase effective parallelism of the application. Thorough discussion on dependece can be read here @ Data Dependence Lecture Notes.

There are multiple types of dependencies, as shown below.

• Algorithm Specific - It can not be resolved, change in algorithm required to increase performance.

• Coding Style Specific - Depends on Code Writing Style and nuances of language. There may be unnecessary assignments or Pointer Aliasing in the code. Few can be resolved easily but some may require complex analysis of the system. However, High Level Synthesis tool must be able to handle this to achieve required effectiveness.

• Somewhat related to coding style, these limitations are because of development plateform, for example output dependence. These are minor irritants but can be handled effectively.

Once dependeces are resolved effectively, next issue is effective distribution/partition of the resources. Any partitioning algorithm for high level synthesis should be able to handle following

• Ability to look at resource cost from multiple perspective.
• Ability to combine related resources so that effective sharing can be performed
• Ability to pipeline a resource to meet timing requirements
• Ability to combine two unrelated resources so that area of combined resource is less than sum of area of individual resources.
• Ability to make tradeoff based on timing, latency and area.

In High Level Synthesis world, effectiveness of any tool depends on  its ability to extract parallelism, inherent in the application. There has been lots of observation on parallelism, originating, mainly with Amdahl's Law. Amdahl's Law is very passimistic observation and similar empirical analysis is performed in Limits of Instruction Level Parallelism. This research paper is very old, written in 1993. However, findings are still applicable. Excerpts from Paper:

Growing interest in ambitious multiple-issue machines and heavilypipelined machines requires a careful examination of how much instructionlevelparallelism exists in typical programs. Such an examination is complicated by the wide variety of hardware and software techniques for increasingthe parallelism that can be exploited, including branch prediction, register renaming, and alias analysis. By performing simulations based on instructiontraces,  we can model techniques at the limits of feasibility and evenbeyond. This paper presents the results of simulations of 18 different testprograms under 375 different models of available parallelism analysis.

Bottleneck according to Amdahl, is because of strictly dependent/serial portion of any code. Considering a infinite parallel computer, minimum time to execute an application is dependent on strictly serial portion because this set of instruction can not be executed in parallel. According to Amdahl's Law, there is no tangible gain whatsoever for computer having more than 10 parallel cores, and in general, 3-4 parallel cores are enough.

However, Gustafson-Barsis' law looks at parallelism in different way. This is more optimistic view on parallelism. Accodring to this law,  parallelism scales well with increasing complexity. Or in other words, any sufficiently large problem can be efficiently parallelized.

Above observations are based on mainly spatial parallelism, inherent in application i.e. executing two pieces of code in parallel at different coordinates on a given computing plateform. There is another set of parallelism which can be exploited in time, called temporal parallelism. Main example is pipelining in computers, which runs three or four (some upto 10-12) instruction at a time but ingress to system is one instruction at a time and egress is one result at a time. Effective execution cycles for an instruction is increased but effective execution time for application is shortened i.e. both throughput and latancy are increased.

Both, spatial and temporal are still looked as different aspects in computing world but I believe that both spatial and temporal parallelism can be combined in effective manner to achieve high performance. Assuming that there is an infinite temporal/spatial parallel computer then theoritically we should be able to achieve throughput of a clock cycle for any complex algorithm (Except for true K-cyclic/cyclic portion of the code).

My conclusion: A virtual infinite temporal/spatial parallel computer can be built for given performance and given application.