Handling of packet dependencies: a critical issue for highly parallel network processors

Network processors are being asked to perform increasingly complex operations on packets of information at faster and faster rates. Because processor performance and memory cycle times are not keeping up with this demand, there is a fundamental need for simultaneous processing of multiple packets, and the degree of this parallelism is increasing. Sometimes a dependency exists between two packets currently being operated on, and as the ratio of packet processing time to packet transmission time increases, these dependencies are more likely to impact performance. Thus, the way packet dependencies are handled will become critical. In this paper we show that there is potentially a dramatic difference in performance between optimal and non-optimal solutions. We argue that this is the key challenge that must be addressed in highly parallel network processors. We discuss how work in thread level speculation relates to this problem and describe a practical hardware implementation that requires little or no changes to software and with near optimal performance