Efficient reconfigurable techniques for VLSI arrays with 6-port switches

This paper proposes an efficient techniques to reconfigure a two-dimensional degradable very large scale integration/wafer scale integration (VLSI/WSI) array under the row and column routing constraints, which has been shown to be NP-complete. The proposed VLSI/WSI array consists of identical processing elements such as processors or memory cells embedded in a 6-port switch lattice in the form of a rectangular grid. It has been shown that the proposed VLSI structure with 6-port switches eliminates the need to incorporate internal bypass within processing elements and leads to notable increase in the harvest when compared with the one using 4-port switches. A new greedy rerouting algorithm and compensation approaches are also proposed to maximize harvest through reconfiguration. Experimental results show that the proposed VLSI array with 6-port switches consistently outperforms the most efficient alternative proposed in literature, toward maximizing the harvest in the presence of fault processing elements.     

Communication-aware heuristics for run-time task mapping on NoC-based MPSoC platforms

Efficient run-time mapping of tasks onto Multiprocessor System-on-Chip (MPSoC) is very challenging especially when new tasks of other applications are also required to be supported at run-time. In this paper, we present a number of communication-aware run-time mapping heuristics for the efficient mapping of multiple applications onto an MPSoC platform in which more than one task can be supported by each processing element (PE). The proposed mapping heuristics examine the available resources prior to recommending the adjacent communicating tasks on to the same PE. In addition, the proposed heuristics give priority to the tasks of an application in close proximity so as to further minimize the communication overhead. Our investigations show that the proposed heuristics are capable of alleviating Network-on-Chip (NoC) congestion bottlenecks when compared to existing alternatives. We map tasks of applications onto an 8 × 8 NoC-based MPSoC to show that our mapping heuristics consistently leads to reduction in the total execution time, energy consumption, average channel load and latency. In particular, we show that energy savings can be up to 44% and average channel load is improved by 10% for some cases.     

An efficient algorithm for the collapsing knapsack problem

The collapsing knapsack problem (CKP) is a type of nonlinear knapsack problem in which the knapsack size is a non-increasing function of the number of items included. This paper proposes an exact algorithm for CKP by partitioning CKP to some subproblems, then solving them with the improved expanding-core technique. The proposed algorithm solves the subproblems in the special processing order resulting in the reduction of computing time. Experimental results show that the proposed algorithm is an efficient approach for various random instances of size up to 1000.     

Heuristic techniques for accelerating hierarchical routing on road networks

The route computation module is one of the most important functional blocks in a dynamic route guidance system. Although various algorithms exist for finding the shortest path, their performance tends to deteriorate as the network size increases. We present an efficient hierarchical routing algorithm that finds a near-optimal route and evaluate it on a large city road network. Solutions provided by the hierarchical routing algorithm are compared with the optimal solutions to analyze and quantify the loss of accuracy. We propose a novel yet simple heuristic to substantially improve the performance of the hierarchical routing algorithm with acceptable loss of accuracy. A network pruning technique has been incorporated into the algorithm to reduce the search space and the correctness of the results is evaluated. The improved hierarchical routing algorithm that incorporates the heuristic techniques has been found to be over 50 times faster than a typical shortest path algorithm.     

Efficient heuristic and tabu search for hardware/software partitioning

Hardware/software (HW/SW) partitioning is a crucial step in HW/SW codesign that determines which components of the system are implemented on hardware and which ones on software. It has been proved that the HW/SW partitioning problem is NP-hard. In this paper, we present two approaches for HW/SW partitioning that aims to minimize the hardware cost while taking into account software and communication constraints. The first is a heuristic approach that treats the HW/SW partitioning problem as an extended 0–1 knapsack problem. In the second approach, tabu search is used to further improve the solution obtained from the proposed heuristic algorithm. Experimental results show that the proposed algorithms outperform a recently reported work by up to 28 %.     

Novel algorithm for Clos-type networks

A new routing algorithm for controlling nonblocking Clos-type permutation networks is presented. Unlike previous algorithms based on matrix decomposition and looping techniques, the algorithm uses a new method called scheduling, does not use iterations, and has execution time 0(Nr/sup 1/2/) where N is the total number of ports, and r is the number of first-stage switches.<>     

Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design

Hardware/software (HW/SW) partitioning and scheduling are the crucial steps during HW/SW co-design. It has been shown that they are classical combinatorial optimization problems. Due to the possible sequential or concurrent execution of the tasks, HW/SW partitioning and scheduling has become more difficult to solve optimally. In this paper more efficient heuristic algorithms are proposed for the HW/SW partitioning and scheduling. The proposed algorithm partitions a task graph by iteratively moving the task with highest benefit-to-area ratio in higher priority. The benefit-to-area ratio is updated in each iteration step to cater for the task concurrence. The proposed algorithm for task scheduling executes the task lying in hardware-only critical path in higher priority to enhance the task forecast. A large body of experimental results conclusively shows that the proposed heuristic algorithm for partitioning is superior to the latest efficient combinatorial algorithm (Tabu search) cited in this paper. Moreover, the Tabu search for partitioning has been further improved by utilizing the proposed heuristic solution as its initial solution. In addition, the proposed scheduling algorithm obtains the improvements over the most widely used approaches by up to 10% without large increase in running time. This work was presented in part at 2006 IEEE International Conference on Field Programmable Technology (ICFPT).     

CADSE: communication aware design space exploration for efficient run-time MPSoC management

Real-time multi-media applications are increasingly mapped on modern embedded systems based on multiprocessor systems-on-chip (MPSoC). Tasks of the applications need to be mapped on the MPSoC resources efficiently in order to satisfy their performance constraints. Exploring all the possible mappings, i.e., tasks to resources combinations exhaustively may take days or weeks. Additionally, the exploration is performed at design-time, which cannot handle dynamism in applications and resources’ status. A runtime mapping technique can cater for the dynamism but cannot guarantee for strict timing deadlines due to large computations involved at run-time. Thus, an approach performing feasible compute intensive exploration at design-time and using the explored results at run-time is required. This paper presents a solution in the same direction. Communicationaware design space exploration (CADSE) techniques have been proposed to explore different mapping options to be selected at run-time subject to desired performance and available MPSoC resources. Experiments show that the proposed techniques for exploration are faster over an exhaustive exploration and provides almost the same quality of results.     

Network Simulation Environment (NSE): A Generic Framework for Network Graphs

A Network Simulation Environment (NSE) tool for identifying various routes within the network graphs based on clustering concept is proposed. The proposed tool is designed using object-oriented approach in Microsoft Windows environment. It allows the user to create, modify and display network graphs. One of the main features of the simulation package is the visualisation of the clustering of the graph to the acyclic level. It shows the step by step clustering of the network graph. The reverse process of unclustering is also featured in the proposed package. It offers a generic framework for comparing different types of routing algorithms by computing routing times and many other attributes for various algorithms. In addition, the simulation package provides facilities for printing and saving the network graphs.     

Static Modeling of GMAW Process Using Artificial Neural Networks

Due to the complexity of the welding process, neural network based approach is being considered as an effective way to represent the required model. This paper describes the steps adopted to construct the neural network model for GMAW (Gas Metal Arc Welding) welds. A detailed analysis of the simulation results has been carried out to evaluate the proposed neural network model. Some practical considerations that may come across in the modeling process are also discussed. Finally, a suitable proposal to improve the construction of the model has also been presented in the paper.