Research

The scope of LS 12 is computer engineering. Research at LS XII covers different areas in computer-aided design (CAD) of digital integrated circuits and systems. Emphasis is on high levels of abstraction and the use of programmable components.

Current research activities include the following areas:

1. Compilers and code generation for embedded processors

The use of embedded processors poses new challenges for software compilers, because real-time constraints and limited silicon area for program memories demand for extremely efficient machine code. Current compiler technology does not meet these demands. In particular, this holds for the area of digital signal processing (DSP) where application-specific processors with peculiar instruction sets are predominant. As a consequence, the largest part of DSP software is still developed manually at the assembly-language level. Our research efforts aim at eliminating this bottleneck by providing novel compiler technology and tools that permit the use of compilers also for embedded system design. We are developing novel code generation and optimization techniques, with emphasis on DSPs, which are capable of generating high-quality machine code. In addition, we are working on methods for model-based retargetable compilation. Our research has led to a total of four books, published in 1995, 1997, 2000 and 2001, respectively. 



• Source Code Optimization Techniques for Data Flow Dominated Embedded Software

The building blocks os today's embedded systems-on-a-chip (SoC) are complex IP components and programmable processor cores. This means that more and more system functionality is implemented in software rather than in custom hardware motivating the need for highly optimized embedded software.

The source code optimization techniques developed at LS XII focus on the application of optimizations outside a compiler at the source code level. LS XII research in this domain covers the following areas:

	Several entirely new techniques were developed in combination with efficient algorithms for the most important ones.
	Control flow analysis and optimization of data-dominated applications is one of the main contributions of our research since this issue remained open up to now.
	Using real-life applications, large improvements in terms of runtimes and energy dissipation were achieved by our research. Detailed results for a broad range of processors including DSPs, VLIWs and embedded RISC cores are reported.

For more detailed information, click here. 

• LANCE machine-independent compiler frontend for C
  For further information, click here. (ICD website) 
  


• Generic Low-Level Intermediate Representation (GeLIR)

For more detailed information, click here. 


• Low-power/low-energy code generation

For portable information processing equipment, low energy consumption is extremely important. This importance will continue since only small improvements are expected for battery technologies. Due to the cost of cooling, power supplies and packages, low energy consumption is also important for non-portable equipment. At LS 12, we are exploring the extent to which compilers can contribute towards a reduced energy consumption of software. The largest potential is in exploiting the memory hierarchy, but other opportunitiues exist as well. As an example, we have developed the encc energy aware compiler for ARM processors.   


• Code generation for very long instruction word machines
  Very long instruction word machines are machines controlling a variety of functional units (adder, multipliers etc) from a very long (64..256 bits) instruction word (VLIW). For VLIW machines,  the compiler is responsible for finding operations that can be executed in parallel. This avoids a lot of hardware overhead that is required for run-time detection of possible parallelism and also allows a more global view at the application. If compared to standard processors, VLIW parallelism can be used to improve the performance or to clock frequency. The latter allows reducing also  the power supply voltage, resulting in energy savings. VLIW processors require special compilation techniques, which are the subject of some of our research efforts (see e.g. paper in inlining ICCAD and exploitation of predicated execution ). 



• Phase coupling using constraint logic programming
  Every compiler consists of a number of phases. Each phases is solving a particular problem. Typical phases include instruction selection, register allocation, and instruction scheduling. For standard RISC processors, the code quality does not suffer significantly from keeping these phases essentially independent. However, for embedded processors, this is different. Due to the need for efficient designs, embedded processors include specialized features such as complex instructions and heterogeneous register files. With such features, it is more important to couple theses phases. This is very difficult if conventional, imperative programming is used. In contrast, constraint logic programming (CLP, an extension of logic programming) provides compact mechanisms for describing constraints. As a result, possible results of one compiler phases as well as constraints to be respected by these results can be represented conveniently in CLP and forwarded to the next compiler phase. Using this idea, several compilers have been designed and it has been shown that they can generate very compact code, sometimes even outperforming human assembly language programmers (see e.g. Constraint Driven Code Selection for Fixed-Point DSPs).



• Code generation for network processors
  Computers in a network typically use bit-serial, bit-oriented protocols for communication. With the advent of ISDN and xDSL,  it becomes important to implement such protocols in mass-markets at very low cost. Nevertheless, data rates are increasing at a rapid rate and changing protocols also have to be accomodated. For this reason, specialized bit-oriented processors has received a significant attention. Exploitation of the special features of such processors is only possible with advanced compilation techniques supporting processing of variable-length bit vectors. Such techniques are studied at LS 12.   



• Compiler-based optimization of application-domain-specific processors
  Application specific instruction set processors (ASIPs), being 'processor templates' that are modified by the vendor according to the customers' specification, help shorten the crucial time-to-market for systems where the cost/performance tradeoff plays a major role. At LS 12, the encc compiler was retargeted to generate code for the LEON processor, a SPARC V8 compatible implementation, available as VHDL source code. In the course of the research work, we plan to modify parameters of the LEON's architecture and adapt the compiler to take advantage of these modifications, aimed at producing a low energy system. Considered parameters cover the exploitation of the memory hierarchy (caches and on-chip memories in particular), register files, instruction and data encoding, additional functional units as well as a reduced instruction word length.
 


2. Applications of Multimedia techniques for teaching computer engineering
   There are many cases in which classical presentation techniques are inappropriate for teaching computer engineering. Example include systems that exhibit some dynamics, such as pipelines, multi-level caches and communication systems. Visualization of the dynamic behaviour helps understanding such systems. Simple "movies", however, are not sufficient since user interaction has to be possible in order to really get to know the dynamic behaviour. For example, pipelines have to be filled with different instructions, caches have to be demonstrated with different access patterns. Multimedia technology opens new opportunities for interactive visualization. Developing multimedia-based visualization is the goal of our project Ravi (for German "Rechnerarchitektur-Visualisierung", or computer architecture visualization). Ravi is one project of the more comprehensive Simba-effort for developing multimedia-based training components for computer science education.

1. Behavioural synthesis (or high-level synthesis)

The term "behavioral synthesis" (or "high-level synthesis") denotes the (at least partially) automated generation of the internal structure of a microelectronic system using components of the register-transfer (RT) level. Adders, memories, multiplexers and decoders are examples of such components. Behavioral synthesis is currently being introduced in industry in order to cope with the increasing complexity of designs and the need to reduce design times. The chairman of LS 12 was one of the first researchers who worked on high level synthesis. This work was stimulated by his former advisor, Gerhard Zimmermann, who was one of the inventors of behavioural synthesis. The work initially focussed on the MIMOLA project and was performed at the University of Kiel, Germany. The most recent version of  the MIMOLA hardware description language as well as the corresponding file exchange format TREEMOLA are available online: MIMOLA 4.1 Language Reference Manual, TREEMOLA 4.0 Language Reference Manual.

The main goal of the behavioural synthesis work performed at Dortmund is the integration of library components and the exploition of algebraic properties of operations. A genetic algorithm has been designed which performs this function. The main result of the research performed at Dortmund is the OSCAR high-level synthesis system (see work by Landwehr et al click here ).
 



2. Hardware/software codesign of embedded systems

Many embedded systems are implemented as so-called systems-on-a-chip. Such chips include programmable processors as well as RAM, ROM and special hardware accelerators. The design of such chips requires a detailed analysis of the different design options, such as implementing certain behavior either in hardware or software. At LS 12, a HW/SW codesign tool named COOL has been developed, which supports this type of analysis as well as the overall design of such chips. A key feature of this tool is the precise modelling of cost and performance metrics and increased flexibility during processor selection. 
 


3. Testing of programmable processors

The fact that processors can be programmed can be exploited for running self-test programs on these. For mainframe computers, such programs are known as diagnostics. Generating diagnostics manually is a very tedious process. We have been working on tools which generate such diagnostics automatically from a description of the processor hardware and from test patterns to be applied to internal nodes at those processors. Early work into this direction includes the work by Gert Krueger. Later, Ulrich Bieker extended this idea, implementing key algorithms in a constraint logic programming language. The resulting RESTART tool   is described in some publications. RESTART has also been coupled to a fault simulator and to test pattern generator DUST from the University of Duisburg. The combined system has been called STARDUST .