Custom instruction generation is fast becoming popular as it provides an alternative means to realize application specific processors. In this paper, we propose an efficient methodology for rapid instruction set customization on RISPs (Reconfigurable Instruction Set Processors) using predefined sets of dataflow structures that are based on templates and reusable structures. A novel template selection strategy was employed to reduce the number of templates required for matching by up to 50%, while providing comparable performance with known approaches. It has been shown that custom instructions could be realized through instantiation of a reduced set of pre-designed reusable structures. Experimental results show that a small number of reusable structures can sufficiently cater to custom instruction generation to notably reduce the time required to realize them on configurable hardware. Moreover, based on our evaluations using MiBench benchmark suites, the reusable structures constitute to only 2% of all the custom instruction instances. The custom instructions generated with reusable structures were implemented in FPGA and it is evident that up to 14% area savings with comparable performance can be achieved when compared with conventional implementation approaches. (C) 2006 Elsevier B.V. All rights reserved.