Ett av de viktigaste stegen i konstruktionen av inbyggda system är hårdvara/programvara partitionering, det vill säga att bestämma vilka komponenter i systemet bör genomföras i hårdvara och vilka i programvara. De flesta formuleringar av hårdvaru / programvara partitionering problem är N P-hård, så de flesta forskningsinsatser på hårdvara / programvara partitionering har fokuserat på att utveckla effektiv heuristik. I denna artikel behandlas den kombinatoriska strukturen bakom partitionering av maskinvara/programvara. Två liknande versioner av partitioneringsproblemet definieras, varav den ena visar sig vara N P-hård, medan den andra kan lösas i polynom tid. Detta hjälper till att förstå den verkliga orsaken till komplexitet i hårdvara / programvara partitionering. Dessutom fungerar polynom-tidsalgoritmen som grund för en mycket effektiv ny heuristisk för N P-hårda versionen av problemet. Till skillnad från allmän heuristik såsom genetiska algoritmer eller simulerad glödgning, använder sig denna heurism av problemspecifik kunskap, och kan på så sätt snabbt hitta högkvalitativa lösningar. Dessutom har den den unika egenskapen att den också beräknar lägre gränser på den optimala lösningen. Det demonstreras på flera riktmärken och även stora slumpmässiga exempel på att den nya algoritmen klart överträffar andra heuristiker som i allmänhet tillämpas på partitionering av hårdvara/programvara.
Det allmänna hårdvarupartitioneringsproblemet har visat sig vara NP-hård REF.
Algorithmic aspects of hardware/software partitioning
{'venue': 'TODE', 'journal': None, 'mag_field_of_study': ['Computer Science']}