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.
In order to solve the problem about the partition of Petri net model and subnet division, realize the concurrent execution or simulation runs of Petri net system, the partitioning algorithm of parallel subnet of Petri...
详细信息
ISBN:
(纸本)9781467365932
In order to solve the problem about the partition of Petri net model and subnet division, realize the concurrent execution or simulation runs of Petri net system, the partitioning algorithm of parallel subnet of Petri net is proposed. First, as Petri net system has the characteristics of synchronization and concurrence, provide the place-invariantbased Petri net model partitioning and subnet division conditions and parallelizing analysis;put forward the extended theorem and validation of partitioning condition of parallel subnet;then, provide the formalization of subnet division and the solving process of place invariant and place-invariantbased partitioning algorithm of parallel subnet of Petri net. The experimental results show that the partitioning algorithm of parallel subnet of place-invariant-based Petri net is feasible and effective.
Gathering data from sensors, mobile sink has been adopted in wireless sensor networks (WSN) and wireless sensor and actor network(WSAN) to achieve higher efficiency. With the help of mobile sink, sensors could attain ...
详细信息
ISBN:
(纸本)9780769550886
Gathering data from sensors, mobile sink has been adopted in wireless sensor networks (WSN) and wireless sensor and actor network(WSAN) to achieve higher efficiency. With the help of mobile sink, sensors could attain a much longer lifetime than the past. However, mobile sink introduces new challenges such as large data gathering latency to WSN/WSAN. A lot of research efforts have been devoted to reduce the data gathering time. Cooperated with a novel partition algorithm, a concise and efficient data gathering scheme is proposed here. A given area can be divided into several zones with balanced data gathering latency. By modeling the partitioning problem as a Traveling Salesman Problem (TSP), an algorithm is designed to balance the data gathering latency among all the zones. Then mobile sinks are assigned to these zones separately. The data could be gathered by these mobile sinks parallel thereupon. Extensive simulations are carried out to evaluate our proposed data gathering scheme. Different distribution patterns are considered. Effectiveness of our proposed data gathering scheme is proved by the simulation results.
Capacitated Arc Routing Problem (CARP) is one of the hot issues of logistics research. Specifically, Ranking First Cutting Second (RFCS) could be used. This research proposed a novel partitioning algorithm - the Multi...
详细信息
ISBN:
(纸本)9783319251592;9783319251585
Capacitated Arc Routing Problem (CARP) is one of the hot issues of logistics research. Specifically, Ranking First Cutting Second (RFCS) could be used. This research proposed a novel partitioning algorithm - the Multi-Label algorithm which obtained better TSP paths meeting the backpack limit on the basis of a complete TSP return. In addition, by experimental verification on questions in the standard question database, the experimental results showed that compared with general partitioning algorithms, for the same complete TSP return, many TSP paths with the shortest total length could be obtained by the Multi-Label algorithm.
Bottom-up computation of data cubes is an efficient approach which is adopted and developed by many other cubing algorithms such as H-Cubing, Quotient Cube and Closed Cube, etc. The main cost of bottom-up computation ...
详细信息
ISBN:
(纸本)9783642173127
Bottom-up computation of data cubes is an efficient approach which is adopted and developed by many other cubing algorithms such as H-Cubing, Quotient Cube and Closed Cube, etc. The main cost of bottom-up computation is recursively sorting and partitioning the base table in a worse way where large amount of auxiliary spaces are frequently allocated and released. This paper proposed a new partitioning algorithm, called Double Table Switch (DTS). It sets up two table spaces in the memory at the beginning, where the partitioned results in one table are copied into another table alternatively during the bottom-up computation. Thus DTS avoids the costly space management and achieves the constant memory usage. Further, we improve the DTS algorithm by adjusting the dimension order, etc. The experimental results demonstrate the efficiency of DTS.
Optical access technology has quickly got a worldwide development. Currently,the deployment of equipment and fiber lines in the optical access network need professionals to design. But,because the lack of a unified st...
详细信息
Optical access technology has quickly got a worldwide development. Currently,the deployment of equipment and fiber lines in the optical access network need professionals to design. But,because the lack of a unified standard,it is difficult to make the network reasonable. By analyzing the PON architecture model,this article talks about an improved partitioning algorithm for PON network design. By entering some parameters,it can automatically calculate the number and configuration of OLT,which can help to optimize the network layout,and save the network construction costs.
partitioning is essential in the smart verification process when measurements are conducted using modern instruments, such as a CT scanner. Numerous partitioning methods are commonly designed for scenes rather than fo...
详细信息
partitioning is essential in the smart verification process when measurements are conducted using modern instruments, such as a CT scanner. Numerous partitioning methods are commonly designed for scenes rather than for geometrical products. This paper introduces a novel method to partition geometrical elements from the measured data of the workpiece containing geometrical deviation and refines the points attribution problem at part boundaries. Firstly, a partition algorithm based on the coarse boundaries is presented. Then, a boundary refinement process is proposed to improve the partition result. A measured data set is taken as an example to verify the feasibility of the proposed method.
Network-on-Chip (NoC) supplies a scalable and fast interconnect for the communication between the different IP cores in the System-on-Chip (SoC). With the growing complexity in consumer embedded systems, the emerging ...
详细信息
Network-on-Chip (NoC) supplies a scalable and fast interconnect for the communication between the different IP cores in the System-on-Chip (SoC). With the growing complexity in consumer embedded systems, the emerging SoC architectures integrate more and more components for the different signal processing tasks. Two dimensional Network-on-Chip (2D NoC) becomes a bottleneck for the development of the SoC architecture because of its limitation on the area of chip and the long latency. In this case, SoC research is forcing on the exploration of three dimensions (3D) technology for developing the next generation of large SoC which integrates three dimensional Network-on-Chip (3D NoC) for the communication architecture. 3D design technology resolves the vertical inter-layer connection issue by Through-Silicon Vias (TSVs). However, TSVs occupy significant silicon area which limits the inter-layer links of the 3D NoC. Therefore, the task partitioning on 3D NoC must be judicious in large SoC design. In this paper, we propose an efficient layer-aware partitioning algorithm based on hypergraph (named ELAP-NoC) for the task partitioning with TSV minimization for 3D NoC architecture floorplanning. ELAP-NoC contains divergence stage and convergence stage. ELAP-NoC supplies firstly a multi-way min-cut partitioning to gradually divide a given design layer by layer in the divergence stage in order to get an initial solution, then this solution is refined in convergence stage. The experiments show that ELAP-NoC performs a better capacity in the partitioning of the different numbers of cores which supplies the first step for the 3D NoC floorplanning.
In order to solve the problem about the partition of Petri net model and subnet division, realize the concurrent execution or simulation runs of Petri net system, the partitioning algorithm of parallel subnet of Petri...
详细信息
In order to solve the problem about the partition of Petri net model and subnet division, realize the concurrent execution or simulation runs of Petri net system, the partitioning algorithm of parallel subnet of Petri net is proposed. First, as Petri net system has the characteristics of synchronization and concurrence, provide the place-invariant-based Petri net model partitioning and subnet division conditions and parallelizing analysis;put forward the extended theorem and validation of partitioning condition of parallel subnet;then, provide the formalization of subnet division and the solving process of place invariant and place-invariantbased partitioning algorithm of parallel subnet of Petri net. The experimental results show that the partitioning algorithm of parallel subnet of place-invariant-based Petri net is feasible and effective.
In order to solve the problem about the partition of Petri net model and subnet division,realize the concurrent execution or simulation runs of Petri net system,the partitioning algorithm of parallel subnet of Petri n...
详细信息
In order to solve the problem about the partition of Petri net model and subnet division,realize the concurrent execution or simulation runs of Petri net system,the partitioning algorithm of parallel subnet of Petri net is ***,as Petri net system has the characteristics of synchronization and concurrence,provide the place-invariantbased Petri net model partitioning and subnet division conditions and parallelizing analysis:put forward the extended theorem and validation of partitioning condition of parallel subnet:then,provide the formalization of subnet division and the solving process of place invariant and place-invariantbased partitioning algorithm of parallel subnet of Petri *** experimental results show that the partitioning algorithm of parallel subnet of place-invariant-based Petri net is feasible and effective.
暂无评论