  Customization of processor architectures through Instruction Set Extensions
(ISEs) is an effective way to meet the growing performance demands of embedded
applications. A high-quality ISE generation approach needs to obtain results
close to those achieved by experienced designers, particularly for complex
applications that exhibit regularity: expert designers are able to exploit
manually such regularity in the data flow graphs to generate high-quality ISEs.
In this paper, we present ISEGEN, an approach that identifies high-quality ISEs
by iterative improvement following the basic principles of the well-known
Kernighan-Lin (K-L) min-cut heuristic. Experimental results on a number of
MediaBench, EEMBC and cryptographic applications show that our approach matches
the quality of the optimal solution obtained by exhaustive search. We also show
that our ISEGEN technique is on average 20x faster than a genetic formulation
that generates equivalent solutions. Furthermore, the ISEs identified by our
technique exhibit 35% more speedup than the genetic solution on a large
cryptographic application (AES) by effectively exploiting its regular
structure.
