Affiliations: Department of Computer Science and Engineering,
Shanghai Jiao Tong University, Shanghai 200240, China | School of Computer Science and Engineering, The
University of Aizu, Fukushima 965-8580, Japan | School of Information Science, Korean Bible
University, 16 Danghyun 2-gil, Nowon-gu, Seoul, South Kroea
Abstract: Mobile and wireless networks are the integrant infrastructure of
mobile and pervasive computing that aims at providing transparent and preferred
information and services for people anytime anywhere. In such environments,
end-to-end network bandwidth is crucial to improve user's transparent
experience when providing on-demand services such as mobile video playing. As a
result, powerful computing power is required for networked nodes, especially
for routers. General-purpose processors cannot meet such requirements due to
their limited processing ability, and poor programmability and scalability.
Intel's network processor IXP is specially designed for fast packet processing
to achieve a broad bandwidth. IXP provides a large number of registers to
reduce the number of memory accesses. Registers in an IXP are physically
partitioned as two banks so that two source operands in an instruction have to
come from the two banks respectively, which makes the IXP register allocation
tricky and different from conventional ones. In this paper, we investigate an
approach for efficiently generating balanced bipartite graph and register
allocation algorithms for the dual-bank register allocation in IXPs. The paper
presents a graph uniform 2-way partition algorithm (FPT), which provides an
optimal solution to the graph partition, and a heuristic algorithm for
generating balanced bipartite graph. Finally, we design a framework for IXP
register allocation. Experimental results demonstrate the framework and the
algorithms are efficient in register allocation for IXP network processors.
Keywords: Register allocation, network processor, bipartite graph, mobile and wireless network, register bank
