Patent ID: 7793276

Claim:
A method comprising: configuring one or more processors into a D-stage processor pipeline; constructing a flow network model for the for a sequential network application program; selecting a plurality of preliminary pipeline stages from the flow network model; modifying the preliminary pipeline stages to perform control flow and variable transmission therebetween for transforming the sequential network application program into D-pipeline stages that collectively perform an infinite packet processing stage (PPS) loop of the sequential network application program; and executing the D-pipeline stages in parallel within the D-stage processor pipeline to provide parallel execution of the infinite PPS loop of the sequential network application program, wherein constructing the flow network model comprises: assigning a unique source node and a unique sink node to the flow network model, adding a program node to the flow network model for each strongly-connected component (SSC) node identified in the summary graph of the dependence graph, adding a variable node to the flow network model for each variable that is defined and used by multiple program nodes, adding a control node C to the flow network model for each SSC node identified in the summary graph of the dependence graph as a source of control dependence, generating edges having an associated weight to connect corresponding program nodes to corresponding variable nodes, generating edges having an associated weight to connect corresponding program nodes to corresponding control nodes, and generating edges between the program nodes and one of the source node and the sink node; and wherein generating edges having an associated weight to connect corresponding program nodes to corresponding variable nodes further comprises: (i) selecting a program node N that defines a variable node V, (ii) adding a definition edge from node N to node V with a weight VCost to the flow network model, (iii) repeating (i)-(ii) for each program node N that defines a variable node V, (iv) selecting a program node M that uses a variable node W, (v) adding an edge from the node W to the program node M with an assigned weight of infinity to the flow network model, and (vi) repeating (iv)-(v) for each program node M that uses a variable node W.