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.<>     

Integrating Differentiated Services with ATM

IP in the edge and ATM in the core are commonplace in today's internetworks. The IETF has proposed a new Quality of Service (QoS) mechanism namely Differentiated Services (DiffServ) for IP networks. On the other hand, QoS is an inherent feature in ATM. It is imperative that IP and ATM QoS interoperate efficiently to provide an end-to-end service guarantee. DiffServ provides a class of service named Assured Forwarding (AF) that does not exactly correlate to any of the service categories offered by ATM. AF is targeted towards a range of applications, such as real-time (rt) that do not require a constant bit rate service provided by Expedited Forwarding, and other non-real-time (nrt) applications that expect a service better than best effort. In this paper we propose the mapping of AF to the Variable Bit Rate (VBR) service category in ATM. VBR is suitable because it is available in the form of rt-VBR and nrt-VBR and could be translated appropriately based on the applications. The mapping is implemented and verified using the LBNL Network Simulator. The results of the experiments show that VBR is a better match for AF than any other service category in ATM.     

A quantitative structure-activity relationship study on some sulfolanes and arylthiomethanes acting as HIV-1 protease inhibitors

A quantitative structure-activity relationship (QSAR) study on some sulfolanes and arylthiomethanes acting as human immunodeficiency virus-1 (HIV-1) protease inhibitors reveals that in the case of sulfolanes an octahydropyrindene ring and a five-membered 3(S)-sulfolane ring with a hydrophobic 2-substituent (cis to 3-substituent) will be crucial for the inhibition activity. The binding of a sulfolane, which is a nonpeptidic molecule, with the enzyme is shown to partly mimic the binding of a peptidic inhibitor. The 2-substituent is found to have strong hydrophobic interaction with the receptor. Similarly, in the case of arylthiomethanes, one of the substituents of the methane is found to have strong hydrophobic interaction with the enzyme, while the aryl substituent (4-hydroxy-6-phenyl-2-oxo-2H-pyran-3-yl) is assumed to be involved in the hydrogen bondings.     

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).