Balanced bipartite graph based register allocation for network processors in mobile and wireless networks

Feilong Tang, Ilsun You, Minyi Guo, Song Guo, Long Zheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)65-83
Number of pages19
JournalMobile Information Systems
Issue number1
Publication statusPublished - 1 Jan 2010
Externally publishedYes


  • Bipartite graph
  • Mobile and wireless network
  • Network processor
  • Register allocation
  • Register bank

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Balanced bipartite graph based register allocation for network processors in mobile and wireless networks'. Together they form a unique fingerprint.

Cite this