Veezhinathan Kamakoti

The problem of placement is well known in Computer Aided Design (CAD) of VLSI Chips, DNA Micro arrays and Microfluidic biochips. Because of the similarity of the placement problem across diverse domains a generalization of the same is reported in the literature. The generalized placement problem is an instance of the classical Quadratic Assignment Problem (QAP). In this paper, we present a new randomization based heuristic algorithm for QAP. The key to success of the proposed technique is a novel probability distribution that is employed by the heuristics to generate the necessary randomization. We show through simulation results that the proposed algorithm finds competitive solutions comparable with one of the best heuristics reported in literature, while consuming significantly smaller amount of CPU time. © 2011 IEEE.

This paper introduces a novel parallel evolutionary methodology making use of ANN for solving the spatial partitioning problem for multi-FPGA (field programmable gate arrays) architectures. The algorithm takes as input a HDL (hardware description language) model of the application along with user specified constraints and automatically generates a task graph G; partitions G based on the user specified constraints and maps the blocks of the partitions onto the different FPGAs in the given multi-FPGA architecture, all in a single-shot. The proposed algorithm was successfully employed to spatially partition a reasonably big cryptographic application that involved a 1024-bit modular exponentiation and to map the same onto a network of nine ACEX1K based Altera EP1K30QC208-1 FPGAs. The suggested parallel evolutionary algorithm for the partitioning step was implemented on a 6-node SGI Origin-2000 platform using the message passing interface (MPI) standard. The results obtained by executing the same are extremely encouraging, especially for larger task graphs. © 2003 IEEE.