Register Allocation Compilation Technique for ASIP in 5G Micro Base Stations

The currently available compilation techniques are for general computing and are not optimized for physical layer computing in 5G micro base stations.In such cases,the foreseeable data sizes and small code size are application specific opportunities for baseband algorithm optimizations.Therefore,the special attention can be paid,for example,the specific register allocation algorithm has not been studied so far.The compilation for kernel sub-routines of baseband in 5G micro base stations is our focusing point.For applications of known and fixed data size,we proposed a compilation scheme of parallel data accessing,while operands can be mainly allocated and stored in registers.Based on a small register group(48×32b),the target of our compilation scheme is the optimization of baseband algorithms based on 4×4 or smaller matrices,maximizing the utilization of register files,and eliminating the extra register data exchanging.Meanwhile,when data is allocated into register files,we used VLIW(Very Long Instruction Word)machine to hide the time of data accessing and minimize the cost of data accessing,thus the total execution time is minimum.Experiments indicate that for algorithms with small data size,the cost of data accessing and extra addressing can be minimized.

Timing Error Aware Register Allocation in TS

Timing speculative(TS)architecture is promising for improving the energy efficiency of microprocessors.Error recovery units,designed for tolerating occasional timing errors,have been used to support a wider range of voltage scaling,therefore to achieve a better energy efficiency.More specifically,the timing error rate,influenced mainly by data forwarding,is the bottleneck for voltage down-scaling in TS processors.In this paper,a new Timing Error Aware Register Allocation method is proposed.First,we designed the Dependency aware Interference Graph(DIG)construction to get the information of Read after Write(RAW)in programs.To build the construction,we get the disassemble code as input and suppose that there are unlimited registers,the same way as so-called virtual registers in many compilers.Then we change the disassemble codes to the SSA form for each basic block to make sure the registers are defined only once.Based on the DIG construction,registers were real-located to eliminate the timing error,by loosening the RAW dependencies.We con-struct the DIG for each function of the program and sort the edge of DIG by an increasing weight order.Since a smaller weighted-edge value means that its owner nodes have more frequent access in instruction flows,we expect it in different registers with no read-write dependency.At the same time,we make sure that there are no additional new spill codes emerging in our algorithm to minimize the rate of spill code.A high rate of spill code will not only decrease the performance of the system but also increase the unexpected read-write dependency.Next,we reallocate the reg-isters by weight order in turn to loosen the RAW dependencies.Furthermore,we use the NOP operation to pad the instructions with a minimal distance value of 2.Experiment results showed that the average distance of RAW dependencies was increased by over 20%.

A Novel Register Allocation Algorithm for Testability

In the course of high-level synthesis of integrate circuit, the hard-to-test structure caused by irrational schedule and allocation reduces the testability of circuit. In order to improve the circuit testability, this paper proposes a weighted compatibility graph (WCG), which provides a weighted formula of compatibility graph based on register allocation for testability and uses improved weighted compatibility clique partition algorithm to deal with this WCG. As a result, four rules for testability are considered simultaneously in the course of register allocation so that the objective of improving the design of testability is acquired. Tested by many experimental results of benchmarks and compared with many other models, the register allocation algorithm proposed in this paper has greatly improved the circuit testability with little overhead on the final circuit area.

Improving on Linear Scan Register Allocation

Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the dec- ades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. Our re- search encourages the avoidance of graphing and graph-coloring based on the fact that precise graph-coloring is nondeterministic poly- nomial time-complete （NP-complete）, which is not suitable for real-time tasks. In addition, practical graph-coloring algorithms tend to use polynomial-time heuristics. In dynamic compilation environments, their super linear complexity makes them unsuitable for register allocation and code generation. Existing tools for code generation and register allocation do not completely fulfill the requirements of fast compilation. Existing approaches either do not allow for the optimization of register allocation to be achieved comprehensively with a sufficient degree of performance or they require an unjustifiable amount of time and/or resources. Therefore, we propose a new class of register allocation and code generation algorithms that can be performed in linear time. These algorithms are based on the mathematic- al foundations of abstract interpretation and the computation of the level of abstraction. They have been implemented in a specialized library for just-in-time compilation. The specialization of this library involves the execution of common intermediate language （CIL） and low level virtual machine （LLVM） with a focus on embedded systems.

Register Allocation Algorithm for High-Level Circuit Synthesis for Improved Testability

Register allocation in high-level circuit synthesis is important not only for reducing area, delay, and power overheads, but also for improving the testability of the synthesized circuits. This paper presents an improved register allocation algorithm that improves the testability called weighted graph-based balanced register allocation for high-level circuit synthesis. The controllability and observability of the registers and the self-loop elimination are analyzed to form a weighted conflict graph, where the weight of the edge between two nodes denotes the tendency of the two variables to share the same register. Then the modified desaturation algorithm is used to dynamically modify the weights to obtain a final balanced register allocation which improves the testability of the synthesized circuits a higher fault coverage than other algorithms with Tests on some benchmarks show that the algorithm gives less area overhead and even less time delay.

Global Register Allocation for SIMD Multiprocessors

It is relatively clear how to map regular, repetitive or grid oriented computations onto SIMD architectures. It is not so clear, however, how to do this for irregular computations even though there may be significant amounts of intrinsic parallelism in branch free code. We study compilation techniques for this type of code when targeted to SIMD computers and illustrate their use on a simple model architecture.In this paper, we present one of the compilation techniques, global mpister allocation,we have developed for SIMD computers, and demonstrate that it can effectively allocate registers for parallelizing irregular computations in branch free code. This technique is an extension and a modification of the register allocation via graph coloring approach used by sequential compilers. Our performance results validate our method.

Register Reallocation for Soft Error Reduction

Subsequently to the problem of performance and energy overhead, the reliability problem of the system caused by soft error has become a growing concern. Since register file（RF） is the hottest component in processor, if not well protected, soft errors occurring in it will do harm to the system reliability greatly. In order to reduce soft error occurrence rate of register file, this paper presents a method to reallocate the register based on the fact that different live variables have different contribution to the register file vulnerability（RFV）. Our experimental results on benchmarks from MiBench suite indicate that our method can significantly enhance the reliability.

Legal-Ease:Total Investment Capital & Registered Capital Allocations in China

With the Chinese Government, on a regional basis, specifying “minimum amounts” for registered capital contributions in order to establish foreign-invested enterprises in China, and with a similar occurrence concerning total invested capital requirements,

Using Timed Petri Net to Model Instruction-Level Loop Scheduling with Resource Constraints

This paper uses timed Petri net to model and analyze the problem of instructionlevel loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri net model to integrate functional unit allocation, register allocation and spilling ilno a unified theoretical framework.Then we develop a state subgraph, called Register Allocation Solution Graph, which can effectively describe the major behavior of our new model. The maill property of this state subgraph is that the number of all its nodes is polynomial. Finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity, for almost all practical loop prograrns. Our work lightens a new idea of finding the optimum loop schedules.