A Comparative Analysis of HPL-PD and MIPS Architectures by Using Integrated Approach for IS and RA for Exploiting ILP

A Comparative Analysis of HPL-PD and MIPS Architectures by Using Integrated Approach for IS and RA for Exploiting ILP

Rajendra Kumar (Vidya College of Engineering, Meerut, India)
DOI: 10.4018/IJSSMET.2019040104
OnDemand PDF Download:
No Current Special Offers


In this article, the authors have proposed an integrated algorithm for instruction scheduling and register allocation, and implemented it for compiler optimization in a machine description in a trimaran infrastructure for exploitation of instruction-level parallelism. For this experimental work, the authors added machine descriptions (MDES) targeted to HL-PD architecture. As a result, only a few spills were needed and the quality of the code generated was improved. The application of abstract base graph has been applied for experimental purposes. For these experiments, this article used 20 benchmarks available with trimaran infrastructure for HPL-PD architecture. This article compares some of these results with results obtained performed on LLVM compiler on an MIPS architecture. The implemented algorithm is based on subgraph isomorphism. The input program is represented in the form of directed acyclic graph (DAG). The vertices of the DAG represent the instructions, input, and output operands of the program, while the edges represent dependencies among the instructions.
Article Preview

1. Introduction

For exploitation of instruction level parallelism through compiler optimization it is very important to consider the code optimization and code generation phases efficiently. Instruction scheduling and register allocation (Silva et al., 2012) have great importance in code generation. Recent studies (Castañeda Lozano et al., 2012; Tang et al., 2013) show a lot of efforts on integrated approaches for instruction scheduling and register allocation. The combinations of instruction scheduling and register allocation have been discussed in section 3. The key aspect of proposed technique is the modeling of the hardware resources by redefining the MDES of trimaran infrastructure (Chakrapani et al., 2015) and comparison of results with LLVM compiler. The algorithm is implemented for instruction scheduling and register allocation based on subgraph isomorphism theory (Kumar and Mishra, 2014) on the trimaran compiler for HPL-PD architecture (Kathail, 2000). For the purpose of feasibility and flexibility, the integrated approach is designed for the HPL-PD architecture on the trimaran compiler. This paper is organized as follows: Section 2 presents related work, Section 3 presents use of instruction scheduling and register allocation, Section 4 presents HPL-PD Architecture, Section 5 presents proposed algorithm for instruction scheduling and register allocation, Section 6 presents MDES description steps, Section 7 represents the Experimental results, Section 8 represents the comparison of some of the results with MIPS (Chow, 1998) architecture on LLVM compiler (Lattner and Adve, 2004), Section 9 represents the conclusion and future scope.

The advantage of register allocation is the speed. (Magno and Pereira, 2014) pointed that Register allocation is the optimization technique that can increase efficiency of algorithm up to 250%. As the computers have limited number of CPU registers therefore it is not possible to assign all variables to the registers. A 32-bit variable spilled to memory avails an allocation of 32 bit of stack space. Such variable has a much slower processing speed then a variable in register. (Chaitin et al., 1981) pointed that the spill free register allocation is an NP-Complete problem. They proved that any graph is the interference graph of a program. Graph coloring and Linear scan approaches have been used for register allocation. (Sarkar and Barik, 2007) added a recent work to Linear Scan algorithms called Extended Linear Scan. It applies copy and swap instructions along the source program and uses minimal number of registers to compile the program.

The graph coloring (Björklund et al., 2008) is seen as the optimal approach for register allocation. It has been adopted by several modern compilers like LLVM and Trimaran. A simpler approach linear scan has also been used for the same. The fact by which the minimal coloring to a graph was proved to be NP-Complete (Karp et al., 1972). Subgraph isomorphism is defined as a generalization of graph isomorphism problem which asks whether a graph G isomorphic to graph H. (De La Higuera et al., 2013) computed a subgraph isomorphism problem that has a query complexity of Ω(n3/2). Subgraph isomorphism is seen as a very general form for pattern matching and it provides a platform for several important graph problem, like Hamiltonian paths (Wang et al., 2014), shortest path (Elkin, 2005), cliques (Cheng et al., 2011), etc.

Complete Article List

Search this Journal:
Volume 13: 6 Issues (2022): 2 Released, 4 Forthcoming
Volume 12: 6 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing