[發(fā)明專利]一種基于剩余任務(wù)處理時(shí)間補(bǔ)償?shù)木W(wǎng)絡(luò)處理器負(fù)載均衡調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310612808.0
• 申請(qǐng)日: 2013-11-26
• 公開（公告）號(hào): CN103685053B
• 公開（公告）日: 2017-01-11
• 發(fā)明（設(shè)計(jì)）人: 張建華;王國(guó)棟;李云春;李巍;李靖軒
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): H04L12/803
• 分類號(hào): H04L12/803;H04L12/863
• 代理公司: 北京永創(chuàng)新實(shí)專利事務(wù)所11121
• 代理人: 李有浩

技術(shù)領(lǐng)域

本發(fā)明涉及一種對(duì)網(wǎng)絡(luò)處理器的調(diào)度方法，更特別地說，是指一種基于剩余任務(wù)處理時(shí)間補(bǔ)償?shù)木W(wǎng)絡(luò)處理器負(fù)載均衡調(diào)度方法

背景技術(shù)

網(wǎng)絡(luò)處理器（Notwork?Processor，NP）是新一代用來執(zhí)行數(shù)據(jù)處理和轉(zhuǎn)發(fā)的高速可編程處理器。從功能上講，網(wǎng)絡(luò)處理器主要是完成數(shù)據(jù)處理和轉(zhuǎn)發(fā)任務(wù)。2004年11月第1版《網(wǎng)絡(luò)處理器原理與技術(shù)》張宏科等編著，第1頁(yè)。

為了提高網(wǎng)絡(luò)處理器的性能，解決單核處理器性能的瓶頸，多核處理器應(yīng)運(yùn)而生。多核處理器也稱為片上多核處理器，在同一個(gè)芯片上集成了多個(gè)相同結(jié)構(gòu)的處理核心。多核處理器首先擁有多個(gè)處理核心，利用多線程技術(shù)，整個(gè)處理器的性能是單核處理器的數(shù)倍。多核網(wǎng)絡(luò)處理器存在著大量的數(shù)據(jù)包并行的應(yīng)用，因此數(shù)據(jù)包的調(diào)度是應(yīng)用中影響性能的決定性部分。調(diào)度（dispatch）是指對(duì)于并行或并發(fā)任務(wù)的總的控制。當(dāng)工作開始時(shí)，調(diào)度器將這個(gè)工作分配給指定的處理器或線程。2004年7月第1版《網(wǎng)絡(luò)處理器與網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)》張建忠等譯，第129頁(yè)。

在多核CPU中，必須考慮各個(gè)線程計(jì)算量均衡地分配到各CPU核上的問題，也就是計(jì)算負(fù)載平衡問題。如果線程間的計(jì)算量無法取得好的負(fù)載平衡，那么某些CPU核計(jì)算量大、耗時(shí)多，另外一些CPU核計(jì)算量小、耗時(shí)少；耗時(shí)少的CPU核運(yùn)行完成后，將處于空閑狀態(tài)，導(dǎo)致CPU出現(xiàn)饑餓現(xiàn)象。2009年3月第1版《多核計(jì)算與程序設(shè)計(jì)》周偉明著，第14頁(yè)。

多核CPU對(duì)數(shù)據(jù)處理和轉(zhuǎn)發(fā)任務(wù)是以線速（Line?Rate）對(duì)到達(dá)的數(shù)據(jù)包進(jìn)行處理的，然后對(duì)數(shù)據(jù)包進(jìn)行分類以確定該數(shù)據(jù)包所屬的數(shù)據(jù)流（Flow）。所述數(shù)據(jù)包中的多個(gè)字段可以是源IP地址、目的IP地址、源端口、目的端口、協(xié)議類型等。

基于數(shù)據(jù)包的負(fù)載均衡方案，以數(shù)據(jù)包為單位進(jìn)行分配。基于數(shù)據(jù)流的負(fù)載均衡方案，以數(shù)據(jù)流為單位進(jìn)行分配，即屬于同一數(shù)據(jù)流的數(shù)據(jù)包只能分配到同一個(gè)核進(jìn)行處理。基于數(shù)據(jù)包的負(fù)載均衡存在兩方面的不足：第一，這種方案需要額外的設(shè)計(jì)進(jìn)行數(shù)據(jù)流保序，而且這些保序的設(shè)計(jì)往往會(huì)對(duì)多核處理器性能造成較大影響；第二，由于數(shù)據(jù)包的處理大多需要維護(hù)一張會(huì)話表，基于數(shù)據(jù)包的負(fù)載均衡系統(tǒng)可能將同一個(gè)數(shù)據(jù)流的數(shù)據(jù)包分配到不同引擎上，這會(huì)使得兩個(gè)處理單元同時(shí)訪問一個(gè)數(shù)據(jù)結(jié)構(gòu)的情況，所以需要額外的同步開銷。基于數(shù)據(jù)流的負(fù)載均衡方案不存在上述的不足。

基于數(shù)據(jù)流的負(fù)載均衡方案的不足有：第一，負(fù)載均衡需要知道分配單位的負(fù)載特性，一般多核處理器中可以假設(shè)每個(gè)數(shù)據(jù)包需要的處理能力是基本相同的。而數(shù)據(jù)流是不同的，同屬于一個(gè)數(shù)據(jù)流的數(shù)據(jù)包數(shù)量是無法預(yù)測(cè)的，而且根據(jù)對(duì)互聯(lián)網(wǎng)流量的統(tǒng)計(jì)表明，數(shù)據(jù)流的大小分布很不均衡；第二，一個(gè)數(shù)據(jù)流是由多個(gè)數(shù)據(jù)包組成的，所以基于數(shù)據(jù)流的劃分粒度比較粗，更不容易達(dá)到負(fù)載的均衡。

發(fā)明內(nèi)容

為了解決基于數(shù)據(jù)流的負(fù)載不均衡，本發(fā)明提出一種基于剩余任務(wù)處理時(shí)間補(bǔ)償?shù)木W(wǎng)絡(luò)處理器負(fù)載均衡調(diào)度方法。本調(diào)度方法能夠?qū)⑼粩?shù)據(jù)流分配到多個(gè)處理單元上進(jìn)行并行運(yùn)行，通過對(duì)最小負(fù)載量的處理單元優(yōu)先進(jìn)行數(shù)據(jù)流傳輸，從而實(shí)現(xiàn)網(wǎng)絡(luò)處理器負(fù)載均衡。本發(fā)明方法利用移動(dòng)加權(quán)的策略可以很好的處理流量，降低多核處理器的開銷，提高處理器性能。特別是在出現(xiàn)突發(fā)流量時(shí)，克服數(shù)據(jù)流集中在特定的處理單元進(jìn)行處理。

本發(fā)明是一種基于剩余任務(wù)處理時(shí)間補(bǔ)償?shù)木W(wǎng)絡(luò)處理器負(fù)載均衡調(diào)度方法，該負(fù)載均衡調(diào)度方法包括有下列步驟；

步驟A：數(shù)據(jù)流的關(guān)聯(lián)信息

（A）一個(gè)多核處理器上包括有多個(gè)處理單元，采用集合形式表達(dá)為M＝{m₁,m₂,…,m_K}；K表示處理單元的總個(gè)數(shù)；

（B）一個(gè)多核處理器上運(yùn)行有多條數(shù)據(jù)流，數(shù)據(jù)流采用集合形式表達(dá)為MD＝{F₁,F₂,…,F_X}；X表示運(yùn)行在多核處理器上的數(shù)據(jù)流的總條數(shù)；

設(shè)置數(shù)據(jù)流被調(diào)度完成的時(shí)間，第一條數(shù)據(jù)流F₁被調(diào)度完成的時(shí)間記為第二條數(shù)據(jù)流F₂被調(diào)度完成的時(shí)間記為任意一條數(shù)據(jù)流F_X被調(diào)度完成的時(shí)間記為