高效能對稱式多處理器架構之多層負載平衡機制

A Multi-layered Flow Load Balancing Scheme for High Performance Symmetric Multi-processor Architecture

鄔培麟(Pei-Lin Wu)

指導教授 ： 黃能富

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2007年)

摘要

隨著網路應用的日益成長，新的網路管理設備相繼產生，如入侵防禦系統(IPS)及防火牆(Firewall)。然而，伴隨著網路頻寬倍數於處理器(CPU)計算速度的快速成長，即使以現有最高效能的單一處理器仍無法即時處理龐大的網路資料流量。為了要使網路設備不成為整個的網路瓶頸，許多系統設計師選擇在對稱式多處理器平台(SMP)上進行研發網路設備，期許經由倍數化處理器數量來提升系統效能。然而，隨著處理器數量的增加，許多技術上的瓶頸相繼出現，增加了開發系統的難度以及延長了開發時間。如何克服這些瓶頸並且將網路流量有效率的平均分配到每一顆處理器上成為了重要的議題。
這篇論文主要在提出一個新的系統架構，適用於所有網路管理設備。我們提出了以多層的負載平衡器(Load balancers)來平均分派網路流量到不同的處理器進行運算，同時保持相同連線內的封包先後順序。為了要降低多處理器內Locking機制所帶來的系統負擔，並增加cache的一致性，我們提出Locking-Free的架構，藉由這樣的架構來簡化系統開發的難度。並且提出Early Filtering的機制，藉由快速處理Layer 3封包，來提升整體效能以及降低記憶體使用。隨著處理器數目的增加，更能突顯我們架構的優越性。在經由現實封包的模擬以及驗證下，實驗結果證實了我們的架構可以大幅的提升系統效能，平均化處理器使用率並簡化網路設備開發的流程。

關鍵字

負載平衡 ； 對稱式多處理器架構 ； 平行運算

並列摘要

The continuing Internet bandwidth explosion and the advent of new applications have created great challenges for network forwarding devices, e.g., IPS and Firewall. With network bandwidth doubling about twice as fast as CPU performance, the problem shows. Consequently, more and more systems designers are choosing to distribute the workload across multiple CPUs, using symmetric multi-processing (SMP). Workload distribution is critical to the performance of SMP architecture.
This thesis introduces a novel system to balance the scheduled traffic over multiple processing cores maintaining in-order service. We present a multi-layered load-balancer which provides higher performance and better distribution as number of processors increases. Also, we introduce early filtering mechanism which can higher system performance, decrease memory usage and lower packet latency. Based on measurements of Internet traffic, the simulation results show that our mechanism provides lower average delay and better workload distribution compared with other load-balancing system.

並列關鍵字

Load Balancing ； SMP ； Parallel Computing

參考文獻

[9] David Culler, J.P. Singh, Anoop Gupta, "Parallel Computer Architecture: A Hardware/Software Approach"; Morgan Kaufmann

[12] M. Bjorkman and P. Gunningberg. “Locking effects in multiprocessor implementations of protocols”. In ACM SIGCOMM Symposium on Communications Architectures and Protocols, 1993.

[13] A. Gupta, A. Tucker, and S. Urushibara. “The impact of operating system scheduling policies and synchronization methods on the performance of parallel applications”. In Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 120-132, San Diego, CA, May 1991.

[14] A. Foong, J. Fung and D. Newell. “An In-depth Analysis of the Impact of Processor Affinity on Network Performance”. In IEEE Intl. Conference on Networks, Nov 2004.

[15] J. Salehi, J. Kurose and D. Towsley, "The effectiveness of affinity-based scheduling in multiprocessor network protocol processing", IEEE/ACM Trans. on Networking, vol. 4:4, pp. 516-530, 1996.