Critical Techniques For Register Allocation On IXP Network Processors

As the fast development of the Internet, the traffic over the Internet is increasing explosively. With the advance of telecommunication technology, traffic pressure on network devices is also accumulating. Recent research shows that current capability of network devices is between10Gb/s and 40Gb/s. It's predicted that requirement of the next generation network device is up to 160Gb/s. Traditional devices which are based on general purpose processor and application specific integrated circuit can't catch up with the requirement. There emerge network processors.Network processors (NPs) are tailored to network processing application. They not only can processor packet at high line rate, but also have flexibility and programmability. NPs have special hardware unit for network processing and employ multi-thread multi-processor architecture. To hide memory latency, NPs employ large register file for large number of registers. Intel's IXP network processors partition the register file into 2 banks physically. This allows the operand to be fetched in parallel, as well as constrain the combination of source operands selection. The constraint is that if an instruction specifies two general purpose registers as source operands, they must in different bank respectively.This dissertation researches register allocation on IXP. IXP compiler must deal with register allocation as well as bank assignment, due to the constraint above. Those problem are NP-complete, which are typically resolve with heuristic algorithms and the solution is approximate. Pursuing performance, we design a fixed parameter tractable(FPT-) algorithm to get an optimal solution effectively. Besides, we present a new cost model and some enabling techniques to eliminate redundant code.Experimental results show that the FPT-algorithm can get an optimal solution in short time and have better effort than heuristic algorithm,the improvement is 2.5%.