Optimizing occupied memory of embedded software in the design phase

In this paper, we propose a new method to optimize the occupied memory of embedded software in the design phase based on DSL, T4 and Topological sort. A program is specified as a chain of tasks and the relationship between the tasks. The program is expressed by the dependence graph as a directed graph.
Nội dung trích xuất từ tài liệu:
Optimizing occupied memory of embedded software in the design phaseJournal of Computer Science and Cybernetics, V.28, N.3 (2012), 234244OPTIMIZING OCCUPIED MEMORY OF EMBEDDED SOFTWAREIN THE DESIGN PHASE∗PHAM VAN HUONG, NGUYEN NGOC BINH, PHAM NGOC THANH1 University of Engineering and Technology, Vietnam National University, Hanoi, VietnamTóm t t. Trong xu th¸ ph¡t triºn m¤nh m³ cõa cæng ngh» ph¦n m·m nhóng hi»n nay, v§n · tèi ÷uph¦n m·m nhóng câ vai trá quan trång. Vi»c ¡nh gi¡ v tèi ÷u ph¦n m·m nhóng trong giai o¤nthi¸t k¸ em l¤i nhi·u lñi ½ch. Trong bi b¡o ny, chóng tæi ÷a ra ph÷ìng ph¡p mîi tèi ÷u bë nhîchi¸m döng cõa ph¦n m·m nhóng trong giai o¤n thi¸t k¸ düa tr¶n sp x¸p Tæ-pæ (thù tü Tæ-pæ),ngæn ngú mi·n x¡c ành (DSL) v cæng ngh» sinh m¢ T4. Méi ch÷ìng tr¼nh ÷ñc °c t£ theo mëtchuéi c¡c t¡c vö v quan h» giúa c¡c t¡c vö. Theo â, ch÷ìng tr¼nh ÷ñc biºu di¹n b¬ng mët ç thàphö thuëc cõa chuéi t¡c vö. Méi ¿nh trong ç thà biºu di¹n mët t¡c vö, méi t¡c vö gçm c¡c thængtin °c t£ nh÷ t¶n, ¦u vo, ¦u ra. Méi c¤nh biºu di¹n sü phö thuëc giúa c¡c t¡c vö. Ch÷ìng tr¼nhcâ thº thüc hi»n theo c¡c thù tü Tæ-pæ kh¡c nhau m khæng lm thay êi k¸t qu£ nh÷ng mùc chi¸mdöng bë nhî cõa ch÷ìng tr¼nh s³ kh¡c nhau tr¶n c¡c thù tü Tæ-pæ. Tø ç thà phö thuëc, chóng tæit¼m måi thù tü Tæ-pæ v x¥y düng hm ¡nh gi¡ mùc chi¸m döng bë nhî cõa ch÷ìng tr¼nh theo thùtü Tæ-pæ º chån chuéi Tæ-pæ câ mùc chi¸m döng bë nhî th§p nh§t.Abstract. Nowadays, the optimizing embedded software plays an important role in the developmentof embedded software technology. The evaluation and optimization of embedded software in thedesign phase bring various benefits. In this paper, we propose a new method to optimize the occupiedmemory of embedded software in the design phase based on DSL, T4 and Topological sort. A programis specified as a chain of tasks and the relationship between the tasks. The program is expressed bythe dependence graph as a directed graph. Each node in the directed graph describes a task, whichconsists of specification information such as name, input, output. Each edge describes the relationshipbetween two tasks. The program working by order of tasks in the different Topological orders doesnot change the result, but the occupied memory and performances are different. From the dependencegraph, we can find many topological orders, and each of them will have amount of occupied memoryin difference. Therefore, we built a memory evaluation function to find the topological order that hasthe smallest amount of occupied memory.Keywords. Embedded Software, Optimization, DSL Domain Specific Language, T4 Text Template Transformation Toolkit, Topological Sort, Topological Order, Dependence Graph, Chain ofTasks.∗ This research is partly supported by a VNU scientific project (group A) for 2012-2013.OPTIMIZING OCCUPIED MEMORY OF EMBEDDED SOFTWARE IN THE DESIGN PHASE1.235INTRODUCTIONIn the development of information technology, embedded technology is a very importanttechnology. The embedded system appears in almost fields of social life. Along to the hardwaretechnology, embedded software engineering also has been studied and deeply developed. Theembedded devices are limited on CPU, memory space, battery life [2,13]. Thus, the researchon optimizing the embedded software is especially important.Embedded software optimization is done in the different levels such as the design level, thesource code level, the compiler level and the run-time level [11,14]. Although optimization inthe design phase is a new approach, but it faces many challenges and it brings more benefitsthan the behind phase optimization method. This method is often based on the model drivensoftware engineering. Moreover, software engineering based on DSL and T4 has been widelydeveloped, especially, in specific domain such as embedded software, embedded systems [12,14].The advantages of DSL and T4 are flexibility and strong code generation. In this paper, wepropose an occupied memory optimization method for the embedded software based on Topological sort, DSL and T4. We aim the following objectives: modeling the embedded softwareand generating the parameters from the model automatically; getting all of Topological ordersfrom a dependence graph and evaluating the amount of occupied memory, under each Topological order to select the Topological order that occupy the smallest memory. First, we definea DSL and build the meta-model for modeling the embedded software by a dependence graph.The dependence graph is a directed graph that consists of a set of tasks and the relationshipamong tasks. Second, from this graph, we use the T4 to get information from the model andtransform this information into the mathematical expression of the dependence graph. Then,we find the different Topological orders. Each Topological order describes the execution orderof tasks. The execution of a program by any Topological orders also reaches the same resultbut there are different sizes of occupied memory. Finally, we construct an occupied memoryevaluation function for each Topological order to find the best Topological order.The rest of paper includes following parts: Section 2 Related work; Section 3 Optimizing the memory of embedded software based on Topological sort; Section 4 Developthe framework of DSL, T4 and implement the program that supports optimizing; Section 5 Experimental; Section 6 Conclusion and future work.2.RELATED WORKIn recent years, there are few authors using the DSL to design a model of embedded system.For example, the research [4] defined DSL and developed the framework to specify and designreal-time embedded system. In this paper, [1] the authors also study and develop the DSL forhardware-software co-design based on FPGA. There are some researches on embedded softwareoptimization in the design phase such as the research ...