發(fā)布時間：2018-05-14 21:33

  本文選題：單處理器 + 多資源　； 參考：《東北大學(xué)》2012年博士論文

【摘要】：隨著數(shù)字化進(jìn)程的日益加劇,系統(tǒng)的節(jié)能問題顯得越發(fā)的重要。節(jié)能技術(shù)優(yōu)劣不但影響電池供電嵌入式系統(tǒng)的使用或工作時間,即生命周期(lifetime),而且很大程度上決定了大規(guī)模系統(tǒng)(例如數(shù)據(jù)中心)的電費開銷。為了延長嵌入式系統(tǒng)的生命周期,以及降低大規(guī)模系統(tǒng)的運行成本,在軟件和硬件層次上,大量工作對節(jié)能技術(shù)進(jìn)行了研究。在硬件方面,許多處理器提供了動態(tài)電壓縮放(DVS)的功能,即處理器可以工作在不同的電壓／頻率上。同時,幾乎所有的外圍設(shè)備也支持動態(tài)電源管理(DPM),即設(shè)備具有多種不同的工作狀態(tài)或模式。在軟件方面,通過調(diào)節(jié)系統(tǒng)負(fù)載(任務(wù))在處理器上的工作狀態(tài)、任務(wù)劃分和調(diào)度以及使用外設(shè)的方式來達(dá)到節(jié)能的目的。隨著片外設(shè)備數(shù)量的增加和多核系統(tǒng)的普及,多資源以及多核系統(tǒng)的節(jié)能問題受到了越來越多的關(guān)注。 本文從軟件層面上,主要對單處理器多資源和多核實時系統(tǒng)的節(jié)能問題進(jìn)行深入的研究。首先,在單處理器系統(tǒng)中,根據(jù)設(shè)備和處理器的功耗在系統(tǒng)總體功耗中所占的不同比例,給出不同的解決方法。其次,根據(jù)多核系統(tǒng)不同的劃分以及任務(wù)的不同特性,提出相應(yīng)的解決方法。具體來說,本文工作主要包含以下幾個方面： (1)在處理器功耗占系統(tǒng)功耗主要部分(外設(shè)功耗可忽略或是恒為常量)的單處理器系統(tǒng)中,考慮處理器模式切換的時間和能量開銷,研究能耗敏感的實時任務(wù)調(diào)度及其可調(diào)度性測試條件。首先,提出新的可調(diào)度性測試條件,大大降低了其悲觀性；其次,通過任務(wù)合并消除處理器的空閑模式,大大減少模式切換次數(shù),從而降低功耗；最后,放松對處理器在每個協(xié)周期內(nèi)對休眠時間的限制,使算法適用于更多類型的處理器。 (2)針對外設(shè)功耗處于系統(tǒng)整體功耗的決定性部分的嵌入式系統(tǒng),研究了典型的無線傳感器網(wǎng)絡(luò)(WSN)的節(jié)能問題。無線傳感器網(wǎng)絡(luò)己經(jīng)在監(jiān)控系統(tǒng)等應(yīng)用中被廣泛采用,因為傳感節(jié)點往往是由電量有限的電池供電,所以,如何恰當(dāng)?shù)目刂泼總�傳感節(jié)點的能量消耗從而最大化WSN的生命周期是至關(guān)重要的。本文研究輸油管道監(jiān)控系統(tǒng)中傳感器節(jié)點的線性布置問題,目的是最大化該WSN的生命周期。對于簡單的等距布置方式,首先,說明基于被普遍接受的理想功耗模型的一個結(jié)論(增加傳感器節(jié)點可以增加WSN的生命周期)并不適用于真實的功耗模型；然后,研究等功耗放置方式,并將該問題建模為混合整數(shù)線性規(guī)劃(MILP)；最后,提出兩個高效的啟發(fā)式算法,從相反的方向搜索各傳感節(jié)點工作的功耗等級。與等距放置策略相比,提出的兩個啟發(fā)式算法大大的降低了系統(tǒng)能耗,有效地平衡了各傳感節(jié)點的能耗,顯著的增加了WSN的生命周期。其中一個算法的結(jié)果與MILP的最優(yōu)解幾乎相同。 (3)在處理器與外設(shè)功耗相當(dāng)?shù)南到y(tǒng)中,研究單處理器多外設(shè)實時系統(tǒng)的節(jié)能調(diào)度問題。具體工作主要包含兩個部分。首先,對于簡單的基于幀的周期任務(wù),針對連續(xù)和離散處理器頻率模型,本文分別提出高效的算法,通過計算使系統(tǒng)運行能耗最小的處理器最優(yōu)頻率和設(shè)備最優(yōu)空閑時間,來實現(xiàn)全系統(tǒng)節(jié)能。其次,本文研究具有固定數(shù)量實時任務(wù)和固定數(shù)量外設(shè)的系統(tǒng),考慮不可忽略的設(shè)備轉(zhuǎn)換時間和能耗開銷,找出能耗最優(yōu)調(diào)度,包括任務(wù)的執(zhí)行順序,任務(wù)的運行頻率以及設(shè)備狀態(tài)轉(zhuǎn)換的時間點。對于不同的系統(tǒng)配置,分別采用數(shù)學(xué)規(guī)劃結(jié)合啟發(fā)式算法的方式解決該問題,實驗結(jié)果表明提出的算法大大降低了系統(tǒng)的能耗。 (4)對于多核實時系統(tǒng),研究劃分為簇(cluster)或島(island)的多核體系結(jié)構(gòu)的節(jié)能調(diào)度問題,這種體系結(jié)構(gòu)下,每個島上的所有處理器(核)具有相同的工作電壓和頻率。該研究綜合考慮了系統(tǒng)的時間和頻率約束,對實時任務(wù)提出能耗最小化的調(diào)度算法。首先,證明在不考慮時間約束的情況下,每個島的能耗最小化的最優(yōu)頻率并不依賴于映射到該島上的負(fù)載,而是依賴于該島的核數(shù)及其漏電功耗。然后,針對具有時間約束的系統(tǒng),在固定任務(wù)劃分情況下,提出一多項式復(fù)雜度的算法最小化能耗,并證明其最優(yōu)性。最后,給出多項式復(fù)雜度的整體算法來確定系統(tǒng)活躍島的數(shù)量,任務(wù)劃分和任務(wù)頻率分配。實驗表明該算法在節(jié)能方面大大優(yōu)于相關(guān)的方法,并且分析了不同簇劃分的節(jié)能效果。 (5)研究同質(zhì)多處理器／多核系統(tǒng)并行實時任務(wù)的節(jié)能調(diào)度問題。對于執(zhí)行在固定個數(shù)處理器上的并行任務(wù),首先,提出幾個基于層裝箱(level-packing)的啟發(fā)式任務(wù)調(diào)度算法,大大降低各層內(nèi)的空閑時間；然后,提出一個多項式復(fù)雜度能耗最小化算法,并證明其最優(yōu)性。對于執(zhí)行并行任務(wù)的處理器個數(shù)可以變化的情況,提出另一個多項式復(fù)雜度的算法來確定執(zhí)行各個任務(wù)的處理器個數(shù),任務(wù)調(diào)度以及任務(wù)的頻率分配。實驗結(jié)果表明提出的算法可以大大的降低系統(tǒng)的能耗。 總之,本文綜合研究了單處理器及多處理器系統(tǒng)的節(jié)能技術(shù)。首先,研究單處理器多資源系統(tǒng)的節(jié)能技術(shù),對處理器功耗占主要部分的系統(tǒng),外設(shè)功耗占主要部分的系統(tǒng)以及二者相當(dāng)?shù)南到y(tǒng),分別提出了不同的節(jié)能方法；然后,對于多核實時系統(tǒng),研究了劃分為島的多核系統(tǒng)以及并行實時任務(wù)的節(jié)能調(diào)度問題,大大的降低了系統(tǒng)的能耗。
[Abstract]:With the intensification of the digital process, the energy saving problem of the system becomes more and more important. The advantages and disadvantages of energy saving technology not only affect the use or working time of the battery powered embedded system, that is, the life cycle (lifetime), but also largely determine the cost of electricity in large-scale systems (such as the data center). The life cycle, as well as reducing the operating cost of large-scale systems, studies energy saving technology at the software and hardware levels. On the hardware side, many processors provide the function of dynamic voltage scaling (DVS), that is, the processor can work on different electric voltage / frequency. At the same time, almost all peripheral devices are also supported. Dynamic power management (DPM), that is, a device has a variety of different working states or modes. In software, the purpose of energy saving is achieved by adjusting the working state of the system load (task) on the processor, task division and scheduling, and using peripherals. With the increase of the number of devices and the popularization of multi core systems, many resources are available. The energy saving problem of multi-core system has attracted more and more attention.
From the software level, this paper mainly studies the energy saving problem of single processor multi resource and multi core real-time system. First, in the single processor system, different solutions are given according to the different proportion of the power consumption of the device and the processor in the system overall power consumption. Secondly, according to the different division of the multi-core system, Specific solutions to the different characteristics of tasks are proposed. Specifically, the work of this paper includes the following aspects:
(1) in a single processor system whose power consumption is the main part of the system power consumption (peripheral power consumption is negligible or constant), the time and energy cost of processor mode switching is considered, and the energy sensitive real-time task scheduling and its schedulability test conditions are studied. First, the new schedulability test conditions are proposed, which greatly reduce the test conditions. Pessimism; secondly, eliminating the idle mode of the processor by merging the task, greatly reducing the number of mode switching times and reducing the power consumption; finally, the relaxation time limit for the processor in each co cycle is relaxed, so that the algorithm is suitable for more types of processors.
(2) the energy saving of the typical wireless sensor network (WSN) is studied in the embedded system which is the decisive part of the power consumption in the whole system. The wireless sensor network has been widely used in the application of the monitoring system, because the sensor nodes are often powered by the limited battery, so how to control properly The energy consumption of each sensor node and thus maximizing the life cycle of WSN is essential. This paper studies the linear arrangement of sensor nodes in the pipeline monitoring system to maximize the life cycle of the WSN. For a simple isometric arrangement, first, one is based on a widely accepted ideal power model. The conclusion (increasing the sensor node can increase the life cycle of WSN) is not suitable for the real power consumption model. Then, we study the power placement method and model the problem into mixed integer linear programming (MILP). Finally, two efficient heuristic algorithms are proposed to search the power consumption level of each sensor node from the opposite direction. Compared with the equidistant placement strategy, the proposed two heuristic algorithms greatly reduce the energy consumption of the system, effectively balance the energy consumption of each sensor node, and significantly increase the life cycle of WSN. One of the algorithms is almost the same as the optimal solution of MILP.
(3) the energy saving scheduling problem of the single processor multi peripheral real-time system is studied in the system with the equal power consumption of the processor and peripherals. The specific work includes two parts. First, for the simple frame based periodic task, the efficient algorithm is proposed for the continuous and discrete processor frequency model, and the system runs through calculation. The optimal frequency of the processor and the optimal idle time of the equipment to achieve the whole system energy saving. Secondly, this paper studies a system with fixed number of real-time tasks and fixed number of peripherals, and considers the time and cost of energy consumption that can not be ignored, to find the optimal adjustment of energy consumption, including the sequence of task execution, and the frequency of the task. As well as the time point of the device state conversion, the problem is solved by mathematical programming and heuristic algorithm for different system configuration. The experimental results show that the proposed algorithm greatly reduces the energy consumption of the system.
(4) for multi-core real-time systems, study the energy saving scheduling problem divided into cluster (cluster) or island (Island) multi-core architecture. Under this architecture, all the processors on each island have the same working voltage and frequency. The study takes into consideration the time and frequency constraints of the system, and minimizes energy consumption for real-time tasks. First, it is proved that the optimal frequency of energy consumption minimization of each island does not depend on the load mapped to the island without considering the time constraints, but depends on the number of nuclei and the power leakage of the island. Then, for a system with time constraints, a polynomial complexity is proposed in the case of a fixed task division. The algorithm minimizes energy consumption and proves its optimality. Finally, the overall algorithm of polynomial complexity is given to determine the number of active islands, task division and task frequency distribution. The experiment shows that the algorithm is much better than the related methods in energy saving and analyses the energy saving effect of different cluster division.
(5) to study the energy saving scheduling problem of parallel real-time tasks in homogeneous multiprocessor / multi-core systems. For parallel tasks on a fixed number processor, first, several heuristic task scheduling algorithms based on layer packing (level-packing) are proposed, which greatly reduce the idle time in each layer; then, a polynomial complexity energy consumption is proposed. Minimize the algorithm and prove its optimality. For the change in the number of processors that perform parallel tasks, another polynomial complexity algorithm is proposed to determine the number of processors that perform each task, task scheduling and the frequency allocation of tasks. The experimental results show that the proposed algorithm can greatly reduce the energy consumption of the system.
In conclusion, the energy saving technology of single processor and multi processor system is studied in this paper. Firstly, the energy saving technology of the single processor multi resource system is studied, the system with the main part of the power consumption, the system with the main part of the peripheral power consumption and the two equivalent system, the different energy saving methods are put forward, and then, for the multi kernel, the multi core energy saving technology is put forward. In real time systems, the multi-core system divided into islands and the energy saving scheduling problem of parallel real-time tasks are studied, which greatly reduces the energy consumption of the system.

【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2012
【分類號】：TP332

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 汪林云;劉文軍;;無線傳感器網(wǎng)絡(luò)中帶有移動匯點的能量高效的數(shù)據(jù)收集協(xié)議[J];傳感技術(shù)學(xué)報;2012年05期

2 Hyunwoo Nam;Younghan Kim;;Reactive data collection protocol using mobile sink in wireless sensor network[J];Journal of Measurement Science and Instrumentation;2012年02期

3 葉琳莉;黃日茂;;無線傳感器網(wǎng)絡(luò)管理研究趨勢[J];電腦知識與技術(shù);2011年34期

4 解文斌;鮮明;陳永光;;基于等概率路由模型的傳感器網(wǎng)絡(luò)負(fù)載均衡研究[J];電子與信息學(xué)報;2010年05期

5 孫彥景;田紅;王迎;;多Sink協(xié)同移動的最大化網(wǎng)絡(luò)生存期優(yōu)化算法[J];傳感技術(shù)學(xué)報;2012年10期

6 廖翊丞;唐秋玲;岳岫峪;李賢;鄭莉莉;;一種基于能量受限的移動sink數(shù)據(jù)收集策略[J];廣西大學(xué)學(xué)報(自然科學(xué)版);2013年05期

7 馬維綱;馬建峰;黑新宏;曹源;;基于時間觸發(fā)多傳感器融合的列車測速定位系統(tǒng)可調(diào)度性[J];東南大學(xué)學(xué)報(自然科學(xué)版);2013年06期

8 錢光明;劉_";;限制優(yōu)先次數(shù)的優(yōu)先級調(diào)度算法[J];電腦知識與技術(shù);2013年34期

9 郭君;施宏偉;陳希;;基于時間自動機的跨企業(yè)分層融知系統(tǒng)實時調(diào)度算法[J];系統(tǒng)工程;2013年12期

10 王志強;劉建明;李宏周;彭智勇;;基于TinyOS的非搶占雙環(huán)周期協(xié)同調(diào)度策略[J];桂林電子科技大學(xué)學(xué)報;2014年01期

相關(guān)博士學(xué)位論文 前10條

1 喬穎;實時異構(gòu)系統(tǒng)的集成動態(tài)調(diào)度算法研究[D];中國科學(xué)院軟件研究所;2001年

2 王X;基于異構(gòu)系統(tǒng)的實時數(shù)據(jù)處理[D];中國科學(xué)院研究生院（軟件研究所）;2002年

3 李建國;實時異構(gòu)系統(tǒng)的集成動態(tài)調(diào)度模型與算法研究[D];中南大學(xué);2006年

4 解文斌;面向監(jiān)測應(yīng)用的傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2009年

5 郭首瑋;恒同機上的平行工件在線排序問題[D];上海大學(xué);2010年

6 張希偉;移動式傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集策略研究[D];南京大學(xué);2012年

7 鐘智;具有移動節(jié)點的無線傳感器網(wǎng)絡(luò)定位算法和數(shù)據(jù)收集協(xié)議研究[D];中南大學(xué);2012年

8 王超;無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)收集方法研究[D];北京郵電大學(xué);2012年

9 丁杰;新型高效協(xié)作式移動無線傳感器網(wǎng)絡(luò)技術(shù)研究[D];北京郵電大學(xué);2012年

10 王s，

本文編號：1889524