Q$2.$ Hardware $/$ Software Partitioning

Algorithm $1$ shows the pseudo code of a greedy algorithm for HW$/$SW partitioning. The algorithm starts with a partition where all objects are realized in hardware. Then, objects are migrated to software as long as the performance requirement is satisfied $($function Satisfies Performance$)$ and the cost of the new partitioning is lower $($function f$).$ If an object is migrated, the algorithm also tries to migrate all successor nodes $($function Successors$).$

Algorithm $1$ Pseudo code for a greedy HW$/$SW partitioner

$1$: P $=\{\{\},$ O$\}$ ; $//$all in HW

$2$: procedure Partitioning $($P$)$

$3$: repeat

$4$: Pold$=$P

$5$: for all oi $$ HW do

$6$: Attempt Move $($P$,$ oi$)$

$7$: end for

$8$: until P $==$ Pold

$9$: end procedure

$10$: procedure AttemptMove $($P$,$ox$)$

$11$: if Satisfies Performance $($Move$($P$,$ox$)$ AND $($f$($Move$($P$,$ox$))$