A buffer minimization problem for the design of embedded systems |
| |
| Institution: | 1. Portsmouth Business School, Richmond Building, Portland Street, Portsmouth PO1 3DE, UK;2. Department of Electrical Engineering, COMSATS Institute of Information Technology, Wah Cantonment, Pakistan;3. Manchester Business School, Booth Street West, The University of Manchester, Manchester M15 6PB, UK;4. School of Computer Science, The University of Manchester, Manchester M13 9PL, UK;1. 111 Combat Wing, Hellenic Air Force, N. Aghialos, Greece;2. Systems Optimization Laboratory, Department of Mechanical Engineering, University of Thessaly, Leoforos Athinon, Pedion Areos, 38334 Volos, Greece |
| |
| Abstract: | We consider a set of tasks, each of them is composed by a set of sequential operations, and a set of buffers. Each buffer b is defined between two tasks Ti and Tj, and is managed as a FIFO structure. Some operations from Ti write data to the buffer b, others from Tj get data from b.The writings and readings generate precedence constraints between the operations. The limitation of the size of the buffers generates another set of precedence constraints between them and circuits in the precedence graph may appear. In this case, there is no feasible schedule for the operations. The aim is to determine the size of each buffer such that the global surface of the buffers is minimized and there is no circuit in the precedence graph.We prove that this problem is polynomial for two tasks using a flow algorithm. We also prove that it is NP-complete in the strong sense for three tasks. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
