![A buffer minimization problem for the design of embedded systems [An article from: European Journal of Operational Research]](https://www.ebooknetworking.net/books/B00/0RR/bigB000RR65N2.jpg)
A buffer minimization problem for the design of embedded systems [An article from: European Journal of Operational Research]
Book Details
Author(s)A. Munier Kordon, J.B. Note
PublisherElsevier
ISBN / ASINB000RR65N2
ISBN-13978B000RR65N9
MarketplaceFrance 🇫🇷
Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in . The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.
Description:
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 T"i and T"j, and is managed as a FIFO structure. Some operations from T"i write data to the buffer b, others from T"j 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.
Description:
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 T"i and T"j, and is managed as a FIFO structure. Some operations from T"i write data to the buffer b, others from T"j 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.
