Many partitioning algorithms have been proposed for distributed Very-large-scale integration (VLSI) simulation. Typically, they make use of a gate level netlist and attempt to achieve a minimal cutsize subject to a lo...
详细信息
Many partitioning algorithms have been proposed for distributed Very-large-scale integration (VLSI) simulation. Typically, they make use of a gate level netlist and attempt to achieve a minimal cutsize subject to a load balance constraint. The algorithm executes on a hypergraph which represents the netlist. We propose a design-driven iterative partitioning algorithm for Verilog based on module instances instead of gates. We do this in order to take advantage of the design hierarchy information contained in the modules and their instances. A Verilog instance represents one vertex in the circuit hypergraph. The vertex can be flattened into multiple vertices in the event that a load balance is not achieved by instance-based partitioning. In this case, the algorithm flattens the largest instance and moves gates between the partitions in order to improve the load balance. Our experiments show that this partitioning algorithm produces a smaller cutsize than is produced by hMetis on a gate-level netlist. It produces better speedup for the simulation because it takes advantage of the design hierarchy.
Directional wave spectra generally exhibit several peaks due to the coexistence of wind sea generated by local wind conditions and swells originating from distant weather systems. This paper proposes a new algorithm f...
详细信息
Directional wave spectra generally exhibit several peaks due to the coexistence of wind sea generated by local wind conditions and swells originating from distant weather systems. This paper proposes a new algorithm for partitioning such spectra and retrieving the various systems which compose a complex sea-state. It is based on a sequential Monte-Carlo algorithm which allows to follow the time evolution of the various systems. The proposed methodology is validated on both synthetic and real spectra and the results are compared with a method commonly used in the literature. (c) 2013 Elsevier Ltd. All rights reserved.
We propose a method for conducting parallel state space exploration using grid computing. It is based on a partitioning method for a configuration of multiple hash tables with proven efficiency in reducing the number ...
详细信息
ISBN:
(纸本)9780769551258
We propose a method for conducting parallel state space exploration using grid computing. It is based on a partitioning method for a configuration of multiple hash tables with proven efficiency in reducing the number of address collisions and the amount of required memory. This paper presents the initial results of simulating the method, showing that for specific state spaces, it might be advantageous in reducing cross transitions and consequently reducing exploration time.
This paper presents an electrical network graph partitioning technique that divides a power network into zones. The idea of partitioning is to prevent the propagation of disturbances between zones and avoid cascading ...
详细信息
ISBN:
(纸本)9781467357692;9781467357678
This paper presents an electrical network graph partitioning technique that divides a power network into zones. The idea of partitioning is to prevent the propagation of disturbances between zones and avoid cascading events in response to disturbances. Identifying coherent groups of buses in power electrical networks is crucial to implement efficient control strategies based on partitioning techniques. Furthermore, the coherent buses can be used for model reduction of complex power systems. Graph theory has an excellent capability to simplify large connoted networks such as the case with large power networks. In this paper, graph partitioning algorithm is applied to electrical networks including IEEE 39-bus and IEEE 118-bus. Graphs with and without weights are considered to investigate and compare the results of using graph partition algorithm. Weights in a graph power system can be real, reactive or apparent power transferred between buses. Finally, disturbances are intentionally inserted on the loads to verify the performance of partitioned power network to violation. The results show the performance and ability of graph partitioning when used in conjunction with a large power network.
This paper presents a new way of accurately determining peaks of the MUSIC ("Multiple emitter location and signal parameter estimation," R. O. Schmidt, IEEE Trans. Antennas and Propagation, vol. AP-34, no. 3...
详细信息
This paper presents a new way of accurately determining peaks of the MUSIC ("Multiple emitter location and signal parameter estimation," R. O. Schmidt, IEEE Trans. Antennas and Propagation, vol. AP-34, no. 3, pp. 276-280, Mar. 1986) spectrum, here considered from the point of view of estimating the directions of arrival (DOAs) of narrowband signals. It can be used, with any smart antenna geometry and for any purpose where MUSIC is applicable. The MUSIC algorithm for DOA estimation evaluates the MUSIC spectrum for various angles and chooses the maxima or peaks as the angles of arrival. The values obtained depend on the interval at which the spectrum is evaluated. The coarser the interval, the less accurate are the results in case of MUSIC. To improve accuracy and not depend on the interval, Root-MUSIC (" Direction finding for diversely polarized signals using polynomial rooting," A. J. Weiss and B. Friedlander, IEEE Trans. Signal Processing, vol. 41, no. 5, pp. 1893-1905, May 1993), which involves finding the roots of a polynomial, is available. However, Root-MUSIC is applicable, in its original form, only to uniform linear arrays (ULA). The gold-MUSIC algorithm proposed in this paper is a two-stage process. The first stage evaluates the objective function at coarse intervals and determines peaks followed by an iterative approach based on gold-section univariate (GSU) minimization (algorithms for Minimization Without Derivatives, R. Brent, Englewood Cliffs, NJ, USA: Prentice-Hall, 1983) to find accurate values of the peaks. If the number of peaks found so far is equal to the number of estimated peaks, the algorithm stops with this first stage. The second stage is an iterative step for fine resolution using finer intervals around the peaks found so far for finding peaks that were missing in previous iterations. This paper, also presents a method, based on a partitioning algorithm for estimating the number of emitters. The performance of gold-MUSIC is described, includ
Clustering algorithms have been used to divide genes into groups according to the degree of their expression similarity. Such a grouping may suggest that the respective genes are correlated and/or co-regulated, and su...
详细信息
ISBN:
(纸本)9781614993308;9781614993292
Clustering algorithms have been used to divide genes into groups according to the degree of their expression similarity. Such a grouping may suggest that the respective genes are correlated and/or co-regulated, and subsequently indicates that the genes could possibly share a common biological role. In this paper, four clustering algorithms are investigated: k-means, cut-clustering, spectral and expectation-maximization. The algorithms are benchmarked against each other. The performance of the four clustering algorithms is studied on time series expression data using Dynamic Time Warping distance in order to measure similarity between gene expression profiles. Four different cluster validation measures are used to evaluate the clustering algorithms: Connectivity and Silhouette Index for estimating the quality of clusters, Jaccard Index for evaluating the stability of a cluster method and Rand Index for assessing the accuracy. The obtained results are analyzed by Friedman's test and the Nemenyi post-hoc test. K-means is demonstrated to be significantly better than the spectral clustering algorithm under the Silhouette and Rand validation indices.
A hierarchical and decentralised model predictive control (DMPC) strategy for drinking water networks (DWN) is proposed. The DWN is partitioned into a set of subnetworks using a partitioning algorithm that makes use o...
详细信息
A hierarchical and decentralised model predictive control (DMPC) strategy for drinking water networks (DWN) is proposed. The DWN is partitioned into a set of subnetworks using a partitioning algorithm that makes use of the topology of the network, historic information about the actuator usage and heuristics. A suboptimal DMPC strategy was derived, which consists in a set of MPC controllers, whose prediction model is a plant partition, where each element solves its control problem in a hierarchical order. A comparative simulation study between centralised MPC (CMPC) and DMPC approaches is developed using a case study, which consists in an aggregate version of the Barcelona DWN. Results have shown the effectiveness of the proposed DMPC approach in terms of the scalability of computations with an acceptable admissible loss of performance in all the considered scenarios.
Integrating more functionality in a smaller form factor with higher performance and lower power consumption is pushing semiconductor technology scaling to its limits. Three-dimensional (3-D) chip stacking is touted as...
详细信息
Integrating more functionality in a smaller form factor with higher performance and lower power consumption is pushing semiconductor technology scaling to its limits. Three-dimensional (3-D) chip stacking is touted as the silver bullet technology that can keep Moore's momentum and fuel the next wave of consumer electronics products. This letter introduces a TSV-aware partitioning algorithm that enables higher performance for application implementation onto 3-D field-programmable gate arrays (FPGAs). Unlike other algorithms that minimize the number of connections among layers, our solution leads to a more efficient utilization of the available (fabricated) interlayer connectivity. Experimental results show average reductions in delay and power consumption, as compared to similar 3-D computer-aided design (CAD) tools, about 28% and 26%, respectively.
K-Means is one of the unsupervised learning and partitioning clustering algorithms. It is very popular and widely used for its simplicity and fastness. The main drawback of this algorithm is that user should specify t...
详细信息
ISBN:
(纸本)9783642342882
K-Means is one of the unsupervised learning and partitioning clustering algorithms. It is very popular and widely used for its simplicity and fastness. The main drawback of this algorithm is that user should specify the number of cluster in advance. As an iterative clustering strategy, K-Means algorithm is very sensitive to the initial starting conditions. In this paper, we propose a clustering technique called MaxD K-Means clustering algorithm. MaxD K-Means algorithm auto generates initial k (the desired number of cluster) without asking for input from the user. MaxD K-means also used a novel strategy of setting the initial centroids. The experiment of the Max-D means has been conducted using synthetic data, which is taken from the Llyod's K-Means experiments. The results from the new algorithm show that the number of iteration improves tremendously, and the number of iterations is reduced by confirming an improvement rate is up to 78%.
Piracy on the high seas is a problem of world-wide concern. In response to this threat, the US Navy has developed a visualization tool known as the Pirate Attack Risk Surface (PARS) that integrates intelligence data, ...
详细信息
ISBN:
(纸本)9780982443859
Piracy on the high seas is a problem of world-wide concern. In response to this threat, the US Navy has developed a visualization tool known as the Pirate Attack Risk Surface (PARS) that integrates intelligence data, commercial shipping routes, and meteorological and oceanographic (METOC) information to predict regions where pirates may be present and where they may strike next. This paper proposes an algorithmic augmentation or add-on to PARS that allocates interdiction and surveillance assets so as to minimize the likelihood of a successful pirate attack over a fixed planning horizon. This augmentation, viewed as a tool for human planners, can be mapped closely to the decision support layer of the Battlespace on Demand (BonD) framework [32]. Our solution approach decomposes this NPhard optimization problem into two sequential phases. In Phase I, we solve the problem of allocating only the interdiction assets, such that regions with high cumulative probability of attack over the planning horizon are maximally covered. In Phase II, we solve the surveillance problem, where the area not covered by interdiction assets is partitioned into non-overlapping search regions (e.g., rectangular boxes) and assigned to a set of surveillance assets to maximize the cumulative detection probability over the planning horizon. In order to overcome the curse of dimensionality associated with Dynamic Programming (DP), we propose a Gauss-Seidel algorithm coupled with a rollout strategy for the interdiction problem. For the surveillance problem, we propose a partitioning algorithm coupled with an asymmetric assignment algorithm for allocating assets to the partitioned regions. Once the surveillance assets are assigned to search regions, the search path for each asset is determined based on a specific search strategy. The proposed algorithms are illustrated using a hypothetical scenario for conducting counterpiracy operations in a given Area of Responsibility (AOR).
暂无评论