在本篇論文中，我們提出 Paired-Register Encoding 可以大量增加指令集的暫存器數目，使得編譯器或程式設計師可以使用更多的暫存器來提高程式的效率，更重要的是此指令格式不會增加額外的位元到指令中。利用這方法我們可以將 Alpha 微處理器中暫存器的數目增為原本的4 倍，讓32 位元的指令可以使用的暫存器從32 個增加到 128 個，使得編譯器或程式設計師可以使用128 個暫存器來存放變數或計算結果來提高程式的效率。

而在此我們也需要一個新的 Register Allocation 演算法，來應對我們新的指令格式，使其有效利用額外的暫存器，來達到提升效能的目的。

We proposed a novel register field encoding scheme – ”Paired-Register Encoding”. This scheme significantly increase the number of register which can encode 4x~8x registers with same encoding space. More register can make compiler perform more aggressive optimization to improve the performance of program.

However, the traditional graph-coloring based register allocation can't handle the pair-register encoding. So we proposed a graph-coloring based algorithm for paired-register encoding. Use pair-group interference graph instead of interference graph.

[1] Alpha. Alpha 21264 Processor Technical Reference Manual. http://www.alpha.com.

[2] ARM. ARM Reference Manual. http://www.arm.com.

[3] X. Zhuang, S. Pande, Differential register allocation, In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, pages 57-70, 2005

[4] J.H. Lee, J. Park, S.M. Moon. Securing More Registers with Reduced Instruction Encoding Architectures. In Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’07), pages 417-425, 2007

[5] V.N. Makarov. The integrated register allocator for GCC. In Proceedings of the GCC Developers' Summit 2007, pages 77-90, 2007

[6] G. J. Chaitin, et. al., Register allocation via coloring, In Computer Languages, Vol. 6, pages 47-57, Jan. 1981.

[7] P. Briggs, K. D. Cooper, and L. Torczon, Improvements to graph coloring register allocation, In ACM Transactions on Programming Languages and Systems, Vol. 16, No. 3, pages 428-455, May 1994.

[8] J. Park, S.M. Moon. Optimistic register coalescing. In ACM Transactions on Programming Languages and Systems, Vol. 26, No. 4, pages 735-765 , 2004

[9] F. Chow and J. Hennessy. The Priority-based Coloring Approach to Register Allocation, In ACM Transactions on Programming Languages and Systems, Vol. 12, No. 4, pages 501-536, 1990

[10] A. B. Kempe. On the geographical problem of the four colors. In American Journal of Mathematics, 2(1): pages 193-200, 1879.

[11] V. Sarkar and R. Barik. Extended Linear Scan: an Alternate Foundation for Global Register Allocation. In Proceedings of the 16th international conference on Compiler construction (CC’07), pages 141-155, 2007

[12] T. Austin, E. Larson, and D. Emst. Simplescalar: An infrastruc-ture for computer system modeling. In IEEE Computer, 35(2):59–67, 2002.

[13] J. Park and S.M. Moon. Optimistic register coalescing. In ACM Transactions on Programming Languages and Systems, Vol. 26, No. 4, pages 736-765, 2004

[14] L. George and A.W. Appel. Iterated register coalescing. In ACM Transactions on Programming Languages and Systems, Vol. 18, No. 3, pages 300-324, 1996

[15] B. Scholz, B. Burgstaller, and J. Xue. Minimizing Bank Selection Instructions for Partitioned Memory Architectures. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pages. 201-211 2006.

[16] J.A. Swensen and Y.N. Patt, Hierarchical Registers for Scientific Computers, In Proceedings of the 2nd international conference on Supercomputing, pages. 346-353, 1988.

[17] Bernhard Scholz and Erik Eckstein. Register Allocation for Irregular Architectures. In Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Sysems, pages 139-148. 2002.

[18] Andrew W. Appel and Lal George. Optimal spilling for CISC machines with few registers. In Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 243–253, 2001.