GCCFG (Global Call Control Flow Graph): A data structure for Inter-procedural Optimizations

Description

Software Managed Multicore (SMM) architecture has become a forerunner of multicore processing solutions. However, compiler techniques for SMM architectures require inter-procedural information and analysis. For this analysis, representations of the control-flow and function call information must be represented in a succinct way. A Global Call Control Flow Graph (GCCFG) provides hierarchical representations of entire programs. For simple programs, GCCFG construction is relatively straightforward. Unfortunately, unique transformation structures are needed for more complex programming cases (e.g., programs with cases of loops with multiple exits, intertwined loops, switch statements, and if-then-else statements with exit statements). To accurately represent these complex cases, unique graph transformations are needed.

Researchers at Arizona State University have developed graph transforms for nearly all GCCFC cases. With this technology, users are able to construct a GCCFG for nearly all cases encountered in SMM architecture. Programs are represented in their entirety, but through a hierarchical framework allowing data to be found quickly and easily. This hierarchical framework captures the control-flow as well as function call information of a program in a succinct way. With this technology, inter-procedural analysis of SMM architectures is possible, paving the way for scaling memory hierarchy to hundreds of cores, allowing the hardware to be simpler, scalable, and more power-efficient.

Potential Applications

  • Software Managed Multicore architecture
  • Multicore processing
  • Data management
  • Computer Science
  • Semiconductors
  • Personal Electronics

Benefits and Advantages

  • Scalability – Can be tailored to fit many different types of multicore architectures.
  • Low Cost – Lower overhead for system integration than competing approaches.
  • Speed – Compilation time is an average of 5X faster than typical state-of-the-art code management techniques and an average of 4X faster than typical state-of-the-art stack management techniques.
  • Succinct – Provides a succinct representation of programs; on average 9X smaller than other representation methods.

Download Original PDF

For more information about the inventor(s) and their research, please see

Dr. Avrial Shrivastava's directory webpage

For more information about related technologies, please see

M13-082P: An infrastructure for memory management on LLM multi-core architectures

M13-123P: An Efficient Stack Data Management for Scratchpad Memory based Multi-core Processors

Case ID:
M15-048P
Published:
09-14-2015
Last Updated:
05-10-2018

Patent Information

For More Information, Contact