Proposal of a greedy-GA combined algorithm for data transfer binding problems

The problems faced in the automatic synthesis of hardware from operation de scriptions are the scheduling problem and the allocation problem. The alloc ation problem can be further divided into three interrelated subproblems. I n this paper, we propose an approximation algorithm that applies a hybrid o f a greedy algorithm and a genetic algorithm (GA) to the data transfer bind ing problem. This algorithm uses a maximum weighted clique algorithm to sea rch for the transfer destinations that can be shared by a selector and a GA to search for the bus allocation for the transfer data for general bus-ori ented interconnections. This GA searches for a highly accurate solution in real time by using three greedy algorithms to generate the initial populati on and conducting a local search when the children are generated. The evalu ation of the performance using eight problems showed that although the comp utation time was worse than that of a conventional algorithm, the proposed algorithm yielded a much more accurate solution. (C) 2001 Scripta Technica.