Progressive Simulated Annealing Algorithm for the Pipeline Allocation Problem of Protocol Independent Switch Architecture Chips

Protocol independent switch architecture (PISA) chips allow users to customize protocols and functions according to specific requirements, which has practical significance in the field of network switches. This paper focuses on the pipeline allocation problem of PISA chips, aiming to minimize the number of pipeline stages used by the program basic blocks while satisfying the dependency and resource constraints. An original progressive simulated annealing algorithm is proposed for the problem, which employs a progressive search mechanism to gradually discover better solutions using fewer stages. Experimental results on the benchmark instances obtained from practical programs show that our algorithm outperforms the list scheduling algorithm by achieving better objective values and higher robustness. The main component of the algorithm is also analyzed to better understand its impact on the algorithm performance.