Statistics

We have 1 guest and 1 member online

SVTechie Recommends

powered_by.png, 1 kB
Pointer Aliasing - Designing Hardware with C Based Languages PDF Print E-mail
del.icio.us It | Furl It | Digg It
Written by SVTechie   
CommentsOriginal Article can be read at Designing hardware with C-based languages
By Venkat Krishnaswamy, co-founder and engineering director at Calypto Design Systems, California. Published on 11/14/2005 in EETimes

With increasing design complexity and shortening time-to-market, hardware designers have sought to use higher levels of abstraction for both verification and design. For many hardware engineers, C-based languages (C/C++ or SystemC) have become a means to specify designs for verification, in addition to offering a starting point for implementation.

As designers increasingly use C to RTL design process, their success depends on the availability of a sound methodology and a set of guidelines for coding an effective specification model.

One such guideline is not to use Pointer Aliasing and is main focus of analysis here. Following items are discussed in detail. What is pointer aliasing? Can it be supported in High Level Synthesis Tool? Does it makes sense to support it at all? How much Pointer Analysis should be supported by tool?

Analysis
By SVTechie on November 16, 2005

During execution, when two or more names exist for the same location at some program point, we call them aliases. In a language which allows arbitrary pointers, the problem of determining aliases at a program point is very difficult.

For High Level Synthesis, ANSI-C is best logical choice because of universal usage & low learning curve. Unfortunately, ANSI-C allows arbitrary usage of pointers to access data structures (for example, pointer arithmetic), resulting in hard-to-analyze Pointer Aliases. One possibility is to restrict design space as advised in the article and not to allow Pointer Aliasing at all. But this limits the tool usage and author strongly believes that some "sensible" Pointer Aliases should be supported. Next section tries to define "scope" of Pointer Aliasing by contrasting and then combining programming styles with restriction imposed by Hardware Implementation Requirements.

Pointers can be used in following manner and may have associated Pointer Aliasing.


  1. Pointers to Single Variable
  2. Pointers to Static Arrays
  3. Pointers to dynamically-allocated storage (using malloc)

Analyzing single variable pointers & performing related optimizations are relatively very simple. Analyzing array based aliasing is more difficult. Arrays fall into categories #2 & #3 and analyzing #3 is much harder because there is no easy way of uniquely naming malloced storage.

From resource usage point of view, Hardware is static in nature, since design is burned into silicon forever. Every parameter & resource (for example, loop count, memory size etc) has to be pre-considered and precisely defined by system architects. There is no dynamic memory allocation in hardware*. Hence, Pointers to dynamically allocated storage should not be used, as mentioned in article also. But category #1 & #2 can be and should be supported fully**. User also can be requested to provide information (by using pragma or inline commands) to aid in the analysis of #3.

Analyzing Pointer Aliasing at low level (as against Source Code analysis) is more simple and accurate as false dependencies can be easily detected and eliminated. There is good algorithm to perform Practical and Accurate Low-Level Pointer Analysis, and reference paper can be downloaded from Practical and Accurate Low-Level Pointer Analysis. Reference Material is provided at the end of this analysis also.

*Note 1: Link Memory Managers (LMMs) provide some dynamic memory allocation. This allocation is buffer based and can be considered more static in nature. Anyway LMMs are part of interface description which can not be described efficiently in ANSI-C because of intricate timing dependence. Author firmly believes that ANSI-C will be used for algorithmic description only in next evolution of EDA tools. Interfaces will be eventually commoditized and become part of standard IP library.

**Note 2: Category 3 may be handled if user provide extra information about nature of dynamic allocation. This information is readily available to systems architects anyway. But given the technology state, it can be deferred for later implementations.

Technical Reference

  1. Vincent A. {Guarna Jr.} - A Technique for Analyzing Pointer and
    Structure References in Parallel Restructuring Compilers - Proceedings of the
    International Conference on Parallel Processing Vol. 2, 1988
  2. L. Smith - Vectorizing {C} Compilers: How Good Are They - Proceedings
    of Supercomputing, November 1991
  3. J. Loeliger and R. Metzger and M. Seligman and S. Stroud -
    Pointer Target Tracking - An Empirical Study-Proceedings of Supercomputing,
    November 1991
  4. W. Landi and B. Ryder - A Safe Approximation Algorithm for
    Interprocedural Pointer Aliasing - Proceedings of the {SIGPLAN} '92 Conference
    on Programming Language Design and Implementation, June 1992
  5. M. Emami - A Practical Interprocedural Alias Analysis for an
    Optimizing/Parallelizing Compiler - Masters Thesis, School of Computer
    Science, {McGill} University, September 1993
  6. J. Choi and M. Burke and P. Carini - Efficient Flow-Sensitive
    Interprocedural Computation of Pointer-Induced Aliases and Side-Effects -
    Proceedings of the {ACM} 20th Symposium on Principles of Programming
    Languages, January 1993


Have Comments, Or want to discuss this article, please click here to visit Discussion Forum.


Disclaimer, the evil necessity: Posted views are of author only and this website is no way responsible for any damages caused by usage of this information.
Last Updated ( Tuesday, 23 May 2006 )
 
< Prev
[ Back ]