Journal articles: 'Partitioning and placement algorithms'

1

Ababei, Cristinel. "Speeding Up FPGA Placement via Partitioning and Multithreading." International Journal of Reconfigurable Computing 2009 (2009): 1–9. http://dx.doi.org/10.1155/2009/514754.

Full text

Abstract:

One of the current main challenges of the FPGA design flow is the long processing time of the placement and routing algorithms. In this paper, we propose a hybrid parallelization technique of the simulated annealing-based placement algorithm of VPR developed in the work of Betz and Rose (1997). The proposed technique uses balanced region-based partitioning and multithreading. In the first step of this approach placement subproblems are created by partitioning and then processed concurrently by multiple worker threads that are run on multiple cores of the same processor. Our main goal is to investigate the speedup that can be achieved with this simple approach compared to previous approaches that were based on distributed computing. The new hybrid parallel placement algorithm achieves an average speedup of2.5×using four worker threads, while the total wire length and circuit delay after routing are minimally degraded.

APA, Harvard, Vancouver, ISO, and other styles

2

Areibi, Shawki, and Zhen Yang. "Effective Memetic Algorithms for VLSI Design = Genetic Algorithms + Local Search + Multi-Level Clustering." Evolutionary Computation 12, no. 3 (September 2004): 327–53. http://dx.doi.org/10.1162/1063656041774947.

Full text

Abstract:

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. Memetic Algorithms have been shown to be very effective in solving many hard combinatorial optimization problems. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions improve solution quality on average by 35% for the VLSI circuit partitioning problem and 54% for the VLSI standard cell placement problem.

APA, Harvard, Vancouver, ISO, and other styles

3

Liu, Huiqun, Kai Zhu, and D. F. Wong. "FPGA Partitioning with Complex Resource Constraints." VLSI Design 11, no. 3 (January 1, 2000): 219–35. http://dx.doi.org/10.1155/2000/12198.

Full text

Abstract:

In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing diverse resource types in the new FPGA architectures. We first propose a network flow based method to optimally check whether a circuit or a subcircuit is feasible for a set of available heterogeneous resources. Then the feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementation. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g., logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g., Actel's ES6500 FPGA family).

APA, Harvard, Vancouver, ISO, and other styles

4

Saab, Youssef. "A Fast Clustering-Based Min-Cut Placement Algorithm With Simulated-Annealing Performance." VLSI Design 5, no. 1 (January 1, 1996): 37–48. http://dx.doi.org/10.1155/1996/58084.

Full text

Abstract:

Placement is an important constrained optimization problem in the design of very large scale (VLSI) integrated circuits [1–4]. Simulated annealing [5] and min-cut placement [6] are two of the most successful approaches to the placement problem. Min-cut methods yield less congested and more routable placements at the expense of more wire-length, while simulated annealing methods tend to optimize more the total wire-length with little emphasis on the minimization of congestion. It is also well known that min-cut algorithms are substantially faster than simulated-annealing-based methods. In this paper, a fast min-cut algorithm (ROW-PLACE) for row-based placement is presented and is empirically shown to achieve simulated-annealing-quality wire-length on a number of benchmark circuits. In comparison with Timberwolf 6 [7], ROW-PLACE is at least 12 times faster in its normal mode and is at least 25 times faster in its faster mode. The good results of ROW-PLACE are achieved using a very effective clustering-based partitioning algorithm in combination with constructive methods that reduce the wire-length of nets involved in terminal propagation.

APA, Harvard, Vancouver, ISO, and other styles

5

Shanavas, I. Hameem, and R. K. Gnanamurthy. "Optimal Solution for VLSI Physical Design Automation Using Hybrid Genetic Algorithm." Mathematical Problems in Engineering 2014 (2014): 1–15. http://dx.doi.org/10.1155/2014/809642.

Full text

Abstract:

In Optimization of VLSI Physical Design, area minimization and interconnect length minimization is an important objective in physical design automation of very large scale integration chips. The objective of minimizing the area and interconnect length would scale down the size of integrated chips. To meet the above objective, it is necessary to find an optimal solution for physical design components like partitioning, floorplanning, placement, and routing. This work helps to perform the optimization of the benchmark circuits with the above said components of physical design using hierarchical approach of evolutionary algorithms. The goal of minimizing the delay in partitioning, minimizing the silicon area in floorplanning, minimizing the layout area in placement, minimizing the wirelength in routing has indefinite influence on other criteria like power, clock, speed, cost, and so forth. Hybrid evolutionary algorithm is applied on each of its phases to achieve the objective. Because evolutionary algorithm that includes one or many local search steps within its evolutionary cycles to obtain the minimization of area and interconnect length. This approach combines a hierarchical design like genetic algorithm and simulated annealing to attain the objective. This hybrid approach can quickly produce optimal solutions for the popular benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

6

Yanpei, Liu, Li Chunlin, Yang Zhiyong, Chen Yuxuan, and Xu Lijun. "Performance Guarantee Mechanism for Multi-Tenancy SaaS Service Based on Kalman Filtering." Cybernetics and Information Technologies 15, no. 3 (September 1, 2015): 150–64. http://dx.doi.org/10.1515/cait-2015-0048.

Full text

Abstract:

Abstract This paper proposes a special System Architecture for Multi-tenancy SaaS Service (SAMSS), which studies the performance security issues at the business logic layer and data processing layer respectively. The Kalman filtering Admission Control algorithm (KAC) and the Greedy Copy Management algorithm (GCM) are proposed. At the business logic layer, Kalman filtering admission control algorithm is presented. It uses a Kalman filter to conduct the dynamic evaluation for the CPU resource for multi-tenancy SaaS service and reduces the unnecessary performance expenses caused by direct measurement of CPU resources. At the data processing layer, the Greedy Copy Management algorithm (GCM) is presented. It changes the copy placement as a K-partitioning set partitioning problem and adopts a greedy strategy to reduce the number of times for creating a data copy. Finally, the experimental analysis and results prove the feasibility and efficiency of the algorithms proposed.

APA, Harvard, Vancouver, ISO, and other styles

7

Sminesh, C. N., E. Grace Mary Kanaga, and A. G. Sreejish. "Augmented Affinity Propagation-Based Network Partitioning for Multiple Controllers Placement in Software Defined Networks." Journal of Computational and Theoretical Nanoscience 17, no. 1 (January 1, 2020): 228–33. http://dx.doi.org/10.1166/jctn.2020.8655.

Full text

Abstract:

Software Defined Networks (SDN) divide network intelligence and packet forwarding functionalities between control plane and data plane devices respectively. Multiple controllers need to be deployed in the control plane in large SDN networks to improve performance and scalability. In a multi-controller scenario, finding the adequate number of controllers and their load distribution are open research challenges. In a large-scale network, the control plane load balancing is termed a controller placement problem (CPP). It is observed that of the existing solutions for the CPP, clustering-based approaches provide computationally less intensive solutions. The proposed augmented affinity propagation (augmented-AP) clustering identifies the required number of network partitions and places the controllers such that the distribution of switches to the controller is much better than with existing algorithms. The simulation results show that the computed controller imbalance factor of augmented-AP algorithm outperforms the existing k-means algorithm.

APA, Harvard, Vancouver, ISO, and other styles

8

Li, Jiaqi, Yiqiang Sheng, and Haojiang Deng. "Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking." Applied Sciences 10, no. 10 (May 22, 2020): 3588. http://dx.doi.org/10.3390/app10103588.

Full text

Abstract:

Information-centric networking (ICN) is an emerging network architecture that has the potential to address demands related to transmission latency and reliability in fifth-generation (5G) communication technology and the Internet of Things (IoT). As an essential component of ICN, name resolution provides the capability to translate identifiers into locators. Applications have different demands on name-resolution latency. To meet the demands, deploying name-resolution servers at the edge of the network by dividing it into multilayer overlay networks is effective. Moreover, optimization of the deployment of distributed name-resolution servers in such networks to minimize deployment costs is significant. In this paper, we first study the placement problem of the name-resolution server in ICN. Then, two algorithms called IIT-DOWN and IIT-UP are developed based on the heuristic ideas of inter-layer information transfer (IIT) and server reuse. They transfer server placement information and latency information between adjacent layers from different directions. Finally, experiments are conducted on both simulation networks and a real-world dataset. The experimental results reveal that the proposed algorithms outperform state-of-the-art algorithms such as the latency-aware hierarchical elastic area partitioning (LHP) algorithm in finding more cost-efficient solutions with a shorter execution time.

APA, Harvard, Vancouver, ISO, and other styles

9

Yun, Seung-kook, and Daniela Rus. "Distributed coverage with mobile robots on a graph: locational optimization and equal-mass partitioning." Robotica 32, no. 2 (December 18, 2013): 257–77. http://dx.doi.org/10.1017/s0263574713001148.

Full text

Abstract:

SUMMARYThis paper presents decentralized algorithms for coverage with mobile robots on a graph. Coverage is an important capability of multi-robot systems engaged in a number of different applications, including placement for environmental modeling, deployment for maximal quality surveillance, and even coordinated construction. We use distributed vertex substitution for locational optimization and equal mass partitioning, and the controllers minimize the corresponding cost functions. We prove that the proposed controller with two-hop communication guarantees convergence to the locally optimal configuration. We evaluate the algorithms in simulations and also using four mobile robots.

APA, Harvard, Vancouver, ISO, and other styles

10

Sreenivasa Rao, K., N. Swapna, and P. Praveen Kumar. "Educational data mining for student placement prediction using machine learning algorithms." International Journal of Engineering & Technology 7, no. 1.2 (December 28, 2017): 43. http://dx.doi.org/10.14419/ijet.v7i1.2.8988.

Full text

Abstract:

Data Mining is the process of extracting useful information from large sets of data. Data mining enablesthe users to have insights into the data and make useful decisions out of the knowledge mined from databases. The purpose of higher education organizations is to offer superior opportunities to its students. As with data mining, now-a-days Education Data Mining (EDM) also is considered as a powerful tool in the field of education. It portrays an effective method for mining the student’s performance based on various parameters to predict and analyze whether a student (he/she) will be recruited or not in the campus placement. Predictions are made using the machine learning algorithms J48, Naïve Bayes, Random Forest, and Random Tree in weka tool and Multiple Linear Regression, binomial logistic regression, Recursive Partitioning and Regression Tree (rpart), conditional inference tree (ctree) and Neural Network (nnet) algorithms in R studio. The results obtained from each approaches are then compared with respect to their performance and accuracy levels by graphical analysis. Based on the result, higher education organizations can offer superior training to its students.

APA, Harvard, Vancouver, ISO, and other styles

11

Antoniou, I., V. Borovinsky, A. Butov, V. Mikhov, A. Podobaev, and A. Tikhonov. "A New Parallel Partitioning and Placement Algorithm for ULSI." IFAC Proceedings Volumes 31, no. 20 (July 1998): 915–21. http://dx.doi.org/10.1016/s1474-6670(17)41914-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Zheng, Yali, Da Meng, and Libing Bai. "PCB Network Analysis for Circuit Partitioning." Applied Sciences 12, no. 16 (August 17, 2022): 8200. http://dx.doi.org/10.3390/app12168200.

Full text

Abstract:

The complexity of automatic placement and routing is proportional to the scale of the circuit. Through netlist partition algorithms, printed circuit board (PCB) circuits are divided into different submodules, and the problem scale is effectively reduced in order to obtain the optimal automatic layout and routing. In this paper, we analyze net attributes and potential patterns in netlists through visualization, and propose a heuristic PCB netlist partition approach based on net attributes and potential patterns which we discover from netlists. Our partition approach takes the netlist as input, and module partition set as output. Firstly, the modules are prepartitioned using net attributes. Further, the special patterns in circuits are discovered, and the scattered resistors, capacitors, and other components caused by prepartitioning would be allocated to initial modules by three rules—classifying, matching, and force strategy. Our method is evaluated on 11 PCB netlists which are built manually. Experimental results show that our proposed netlist partition approach significantly outperforms the state of the art on all evaluation indices, which can achieve 80–96% partition accuracy.

APA, Harvard, Vancouver, ISO, and other styles

13

Cheng *, Feng, and Junfa Mao. "An efficient heuristic force directed placement algorithm based on partitioning." International Journal of Electronics 92, no. 7 (July 2005): 427–36. http://dx.doi.org/10.1080/08827510410001694996.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Kaveh, Ali, and Armin Dadras Eslamlou. "An efficient two-stage method for optimal sensor placement using graph-theoretical partitioning and evolutionary algorithms." Structural Control and Health Monitoring 26, no. 4 (January 21, 2019): e2325. http://dx.doi.org/10.1002/stc.2325.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

CHEN, JIANLI, and WENXING ZHU. "A PLACEMENT FLOW FOR VERY LARGE-SCALE MIXED-SIZE CIRCUIT PLACEMENT." Journal of Circuits, Systems and Computers 23, no. 02 (February 2014): 1450016. http://dx.doi.org/10.1142/s0218126614500169.

Full text

Abstract:

The very large-scale integrated circuit (VLSI) placement problem is to determine the exact location of each movable circuit element within a given region. It is a crucial process in physical design, since it affects performance, power consumption, routability, and heat distribution of a design. In this paper, we propose a VLSI placement flow to handle the large-scale mixed-size placement problem. The main idea of our placement flow is using a floorplanning algorithm to guide the placement of circuit elements. It consists of four steps: (1) With the multilevel framework, circuit elements are clustered into blocks by recursively partitioning; (2) a floorplanning algorithm is performed on every level of the blocks; (3) the macro cells are shifted by a macro shifting technique to determine their exact locations; (4) with each macro cell location fixed, a standard cell placement algorithm is applied to place the remaining objects. The proposed approach is tested on the IBM mixed-size benchmarks and the modern mixed-size (MMS) placement benchmarks. Experimental results show that our approach outperforms the state-of-the-art placers on the solution quality for most of the benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

16

Yan, Jin-Tai. "Fuzzy-clustering-based algorithm for circuit partitioning in standard cell placement." Electronics Letters 31, no. 3 (February 2, 1995): 151–52. http://dx.doi.org/10.1049/el:19950121.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

RIESS, BERNHARD M., and ANDREAS A. SCHOENE. "A NEW LAYOUT DESIGN SYSTEM FOR MULTICHIP MODULES." International Journal of High Speed Electronics and Systems 06, no. 03 (September 1995): 509–38. http://dx.doi.org/10.1142/s0129156495000171.

Full text

Abstract:

A new layout design system for multichip modules (MCMs) consisting of three components is described. It includes a k-way partitioning approach, an algorithm for pin assignment, and a placement package. For partitioning, we propose an analytical technique combined with a problem-specific multi-way ratio cut method. This method considers fixed module-level pad positions and assigns the cells to regularly arranged chips on the MCM substrate. In the subsequent pin assignment step the chip-level pads resulting from cut nets are positioned on the chip borders. Pin assignment is performed by an efficient algorithm, which profits from the cell coordinates generated by the analytical technique. Global and final placement for each chip is computed by the state-of-the-art placement tools GORDIANL and DOMINO. For the first time, results for MCM layout designs of benchmark circuits with up to 100,000 cells are presented. They show a small number of required chip-level pads, which is the most restricted resource in MCM design, and short total wire lengths.

APA, Harvard, Vancouver, ISO, and other styles

18

Kiseleva, Elena, Olha Prytomanova, and Liudmyla Hart. "Solving a Two-stage Continuous-discrete Problem of Optimal Partitioning-Allocation with Subsets Centers Placement." Open Computer Science 10, no. 1 (June 27, 2020): 124–36. http://dx.doi.org/10.1515/comp-2020-0142.

Full text

Abstract:

AbstractA two-stage continuous-discrete optimal partitioning-allocation problem is studied, and a method and an algorithm for its solving are proposed. This problem is a generalization of a classical transportation problem to the case when coordinates of the production points (collection, storage, processing) of homogeneous products are continuously allocated in the given domain and the production volumes at these points are unknown. These coordinates are found as a solution of the corresponding continuous optimal set-partitioning problem in a finite-dimensional Euclidean space with the placement (finding coordinates) of these subsets’ centers. Also, this problem generalizes discrete two-stage production-transportation problems to the case of continuously allocated consumers. The method and algorithm are illustrated by solving two model problems.

APA, Harvard, Vancouver, ISO, and other styles

19

Jimenez, Tamara, Armin R. Mikler, and Chetan Tiwari. "A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement." IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans 42, no. 5 (September 2012): 1194–205. http://dx.doi.org/10.1109/tsmca.2012.2183360.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zhao, Qing, Congcong Xiong, and Peng Wang. "Heuristic Data Placement for Data-Intensive Applications in Heterogeneous Cloud." Journal of Electrical and Computer Engineering 2016 (2016): 1–8. http://dx.doi.org/10.1155/2016/3516358.

Full text

Abstract:

Data placement is an important issue which aims at reducing the cost of internode data transfers in cloud especially for data-intensive applications, in order to improve the performance of the entire cloud system. This paper proposes an improved data placement algorithm for heterogeneous cloud environments. In the initialization phase, a data clustering algorithm based on data dependency clustering and recursive partitioning has been presented, and both the factor of data size and fixed position are incorporated. And then a heuristic tree-to-tree data placement strategy is advanced in order to make frequent data movements occur on high-bandwidth channels. Simulation results show that, compared with two classical strategies, this strategy can effectively reduce the amount of data transmission and its time consumption during execution.

APA, Harvard, Vancouver, ISO, and other styles

21

Li, Jianhua, Laleh Behjat, and Andrew Kennings. "Net Cluster: A Net-Reduction-Based Clustering Preprocessing Algorithm for Partitioning and Placement." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26, no. 4 (April 2007): 669–79. http://dx.doi.org/10.1109/tcad.2007.892339.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Phanendra Babu, N. V., P. Suresh Babu, and D. V. S. S. Siva Sarma. "A New Power System Restoration Technique based on WAMS Partitioning." Engineering, Technology & Applied Science Research 7, no. 4 (August 9, 2017): 1811–19. http://dx.doi.org/10.48084/etasr.1197.

Full text

Abstract:

An important feature of a Wide-Area Measurement System (WAMS) is the ability to recover data during a communication failure. This paper presents a novel scheme of partitioning a PMU installed power network into a number of WAMS regions in order to make the power system restoration process simpler. This algorithm also proposes the optimal placement of Phasor Data Concentrators (PDCs) in each region to record the data from PMUs. This paper considers the restoration constraints like transformer equivalent bus, generation-load balance and the observability of region for the partitioning of power system. The proposed scheme is demonstrated with an IEEE-30 bus system. It is then applied on IEEE-39, IEEE-118 bus systems and on a Northern Regional Grid of the Indian Power Grid.

APA, Harvard, Vancouver, ISO, and other styles

23

Baruah, Nirvik, Peter Kraft, Fiodar Kazhamiaka, Peter Bailis, and Matei Zaharia. "Parallelism-Optimizing Data Placement for Faster Data-Parallel Computations." Proceedings of the VLDB Endowment 16, no. 4 (December 2022): 760–71. http://dx.doi.org/10.14778/3574245.3574260.

Full text

Abstract:

Systems performing large data-parallel computations, including online analytical processing (OLAP) systems like Druid and search engines like Elasticsearch, are increasingly being used for business-critical real-time applications where providing low query latency is paramount. In this paper, we investigate an underexplored factor in the performance of data-parallel queries: their parallelism. We find that to minimize the tail latency of data-parallel queries, it is critical to place data such that the data items accessed by each individual query are spread across as many machines as possible so that each query can leverage the computational resources of as many machines as possible. To optimize parallelism and minimize tail latency in real systems, we develop a novel parallelism-optimizing data placement algorithm that defines a linearly-computable measure of query parallelism, uses it to frame data placement as an optimization problem, and leverages a new optimization problem partitioning technique to scale to large cluster sizes. We apply this algorithm to popular systems such as Solr and MongoDB and show that it reduces p99 latency by 7-64% on data-parallel workloads.

APA, Harvard, Vancouver, ISO, and other styles

24

Abdalla, Omar H., Hady H. Fayek, and Abdel Ghany M. Abdel Ghany. "Secondary and Tertiary Voltage Control of a Multi-Region Power System." Electricity 1, no. 1 (September 24, 2020): 37–59. http://dx.doi.org/10.3390/electricity1010003.

Full text

Abstract:

This paper presents techniques for the application of tertiary and secondary voltage control through the use of intelligent proportional integral derivative (PID) controllers and the wide area measurement system (WAMS) in the IEEE 39 bus system (New England system). The paper includes power system partitioning, pilot bus selection, phasor measurement unit (PMU) placement, and optimal secondary voltage control parameter calculations to enable the application of the proposed voltage control. The power system simulation and analyses were performed using the DIgSILENT and MATLAB software applications. The optimal PMU placement was performed in order to apply secondary voltage control. The tertiary voltage control was performed through an optimal power flow optimization process in order to minimize the active power losses. Two different methods were used to design the PID secondary voltage control, namely, genetic algorithm (GA) and neural network based on genetic algorithm (NNGA). A comparison of system performances using these two methods under different operating conditions is presented. The results show that NNGA secondary PID controllers are more robust than GA ones. The paper also presents a comparison between system performance with and without secondary voltage control, in terms of voltage deviation index and total active power losses. The graph theory is used in system partitioning, and sensitivity analysis is used in pilot bus selection, the results of which proved their effectiveness.

APA, Harvard, Vancouver, ISO, and other styles

25

DE CARVALHO, SÉRGIO A., and SVEN RAHMANN. "BETTER GENECHIP MICROARRAY LAYOUTS BY COMBINING PROBE PLACEMENT AND EMBEDDING." Journal of Bioinformatics and Computational Biology 06, no. 03 (June 2008): 623–41. http://dx.doi.org/10.1142/s0219720008003576.

Full text

Abstract:

The microarray layout problem is a generalization of the border length minimization problem, and asks to distribute oligonucleotide probes on a microarray and to determine their embeddings in the deposition sequence in such a way that the overall quality of the resulting synthesized probes is maximized. Because of its inherent computational complexity, it is traditionally attacked in several phases: partitioning, placement, and re-embedding. We present the first algorithm, Greedy+, that combines placement and embedding and that results in improved layouts in terms of border length and conflict index (a more realistic measure of probe quality), both on arrays of random probes and on existing Affymetrix GeneChip® arrays. We also present a detailed study on the layouts of the latest GeneChip arrays, and show how Greedy+ can further improve layout quality by as much as 12% in terms of border length and 35% in terms of conflict index.

APA, Harvard, Vancouver, ISO, and other styles

26

Kundu, Sudeshna, Suchismita Roy, and Shyamapada Mukherjee. "Rectilinear Steiner Tree Construction Techniques Using PB-SAT-Based Methodology." Journal of Circuits, Systems and Computers 29, no. 04 (July 5, 2019): 2050057. http://dx.doi.org/10.1142/s0218126620500577.

Full text

Abstract:

Rectilinear Steiner Tree (RST) construction is a fundamental problem in very large scale integration (VLSI) physical design. Its applications include placement and routing in VLSI physical design automation (PDA) where wire length and timing estimations for signal nets are obtained. In this paper, a pseudo-Boolean satisfiability (PB-SAT)-based approach is presented to solve rectilinear Steiner tree problem. But large nets are a bottleneck for any SAT-based approach. Hence, to deal with large nets, a region-partitioning-based algorithm is taken into consideration, which eventually achieves a reasonable running time. Furthermore, a clustering-based approach is also explored to improve the partitioning of nets by identifying clusters and then applying a heuristic-based approach to get the minimum wire length for each set of the clusters. Experimental results obtained by these techniques show that the proposed algorithm can solve the RST problem very effectively even on large circuits and it outperforms the widely used RST algorithm FLUTE with 3[Formula: see text][Formula: see text][Formula: see text]to 9[Formula: see text][Formula: see text][Formula: see text]speedups.

APA, Harvard, Vancouver, ISO, and other styles

27

Arivudainambi, D., and R. Pavithra. "Vertex coloring approach for Q-coverage problem in wireless sensor network." Journal of Intelligent & Fuzzy Systems 40, no. 5 (April 22, 2021): 8683–95. http://dx.doi.org/10.3233/jifs-191795.

Full text

Abstract:

Wireless Sensor Network (WSN) has emerged recently due to its advancements and applications in various scientific and industrial fields. WSN consists a set of low cost and readily deployable sensors to monitor targets and recognise the physical phenomena. The principal challenge in WSN is to deploy these sensor nodes in optimal positions to achieve efficient network. Such network should satisfy the quality of service requirements in order to achieve high performance levels. Hence, this paper focuses on target Q-coverage problem where each target requires different number of sensors to monitor them. A Sequential Vertex Coloring based Sensor Placement (SVC-SP) algorithm is proposed to determine the number of sensors required and its optimal spot to satisfy the coverage quality requirement. The SVC-SP algorithm determines sensor requirement by partitioning the target set into independent subsets depending on the target’s position and the sensor’s sensing range. Each independent set consists set of targets that are nearer in the network such that a common sensor is sufficient to monitor them. The cardinality of such independent subsets provides the sensor requirement for target coverage. The optimal spot for each target is determined by the mean positioning of the targets in each independent set. This process is repeated until the q-requirement for each target is satisfied. Further, to improve the optimal spot for sensors, the random based SVC-SP algorithm, cuckoo search based SVC-SP algorithm and the genetic algorithm based SVC-SP algorithm are utilized. The simulation results show that genetic algorithm based SVC-SP algorithm performs better than other existing algorithms.

APA, Harvard, Vancouver, ISO, and other styles

28

Kiseleva, E. M., L. L. Hart, O. M. Prytomanova, and S. V. Zhuravel. "Construction of a generalized Voronoi diagram with optimal placement of generator points based on the theory of optimal set partitioning." Matematychni Studii 53, no. 1 (March 17, 2020): 109–12. http://dx.doi.org/10.30970/ms.53.1.109-112.

Full text

Abstract:

The problem of construction of a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of \textit{n}-dimensional Euclidean space is considered. A method is proposed for solving such a problem based on the formulation of the corresponding continuous problem of optimal partitioning of a set in \textit{n}-dimensional Euclidean space with a partition quality criterion that provides the corresponding form of the Voronoi diagram. Further, to solve such a problem, the developed mathematical and algorithmic apparatus is used, the part of which is Shor's \textit{r}-algorithm.

APA, Harvard, Vancouver, ISO, and other styles

29

Kiseleva, Elena M., and Viktoriya A. Stroyeva. "Algorithm of Solving of Nonlinear Continuous Multicomponent Problem of Optimal Set Partitioning with Placement of Subsets Centers." Journal of Automation and Information Sciences 44, no. 2 (2012): 15–29. http://dx.doi.org/10.1615/jautomatinfscien.v44.i2.20.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Shekarian, Seyed Mohammad Hossein, and Morteza Saheb Zamani. "A Trust-Driven Placement Approach: A New Perspective on Design for Hardware Trust." Journal of Circuits, Systems and Computers 24, no. 08 (August 12, 2015): 1550115. http://dx.doi.org/10.1142/s0218126615501157.

Full text

Abstract:

During the last few years, hardware Trojan horses (HTHs) have become one of the most important threats to the security of very large scale integrated (VLSI) chips. Many efforts have been made to facilitate the process of HTH detection, mostly based on the power analysis of chips. The techniques would be more beneficial if trust-driven techniques are used during the system design. Whereas design for hardware trust (DFHT) is one of the fields of interest, most current approaches include ad-hoc and gate-level design techniques. This paper discusses the advantage of physical-level design approaches with integrated strategies for improving the HTH-detection probability. As a proof of concept, a placement technique is presented with the goal of enhancing the ability of HTH detection techniques based on local power signal analysis. Our results show that the background effects on power pads can be leveraged by a simple partitioning-based placement algorithm. Minimizing the background effects leads to a better Trojan-to-background-effect ratio and more (by about 1.7 times) Trojan detectability.

APA, Harvard, Vancouver, ISO, and other styles

31

Fendji, Jean Louis Kedieng Ebongue, and Patience Leopold Bagona. "Fault-Tolerant Placement of Additional Mesh Nodes in Rural Wireless Mesh Networks: A Minimum Steiner Tree Based Centre of Mass With Bounded Edge Length." Transactions on Networks and Communications 9, no. 4 (August 29, 2021): 39–50. http://dx.doi.org/10.14738/tnc.94.10754.

Full text

Abstract:

Wireless mesh networks are presented as an attractive solution to reduce the digital divide between rural and developed areas. In a multi-hop fashion, they can cover larger spaces. However, their planning is subject to many constraints including robustness. In fact, the failure of a node may result in the partitioning of the network. The robustness of the network is therefore achieved by carefully placing additional nodes. This work tackles the problem of additional nodes minimization when planning bi and tri-connectivity from a given network. We propose a vertex augmentation approach inspired by the placement of Steiner points. The idea is to incrementally determine cut vertices and bridges in the network and to carefully place additional nodes to ensure connectivity, bi and tri-connectivity. The approach relies on an algorithm using the centre of mass of the blocks derived after the partitioning of the network. The proposed approach has been compared to a modified version of a former approach based on the Minimum Steiner Tree. The different experiments carried out show the competitiveness of the proposed approach to connect, bi-connect, and tri-connect the wireless mesh networks.

APA, Harvard, Vancouver, ISO, and other styles

32

Kiseleva, Elena M., Lyudmila L. Hart, and Olga M. Prytomanova. "Algorithm for Constructing Voronoi Diagrams with Optimal Placement of Generator Points Based on Theory of Optimal Set Partitioning." Journal of Automation and Information Sciences 52, no. 3 (2020): 1–12. http://dx.doi.org/10.1615/jautomatinfscien.v52.i3.10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Chatzivasili, Stavroula, Katerina Papadimitriou, Vasilis Kanakoudis, and Menelaos Patelis. "Optimizing the Formation of DMAs in a Water Distribution Network Applying Geometric Partitioning (GP) and Gaussian Mixture Models (GMMs)." Proceedings 2, no. 11 (August 3, 2018): 601. http://dx.doi.org/10.3390/proceedings2110601.

Full text

Abstract:

In the last three decades, the need of achieving a reliable water distribution system has become more eminent for both the consumer’s satisfaction and the efficient management of water sources. The purpose of this paper is to provide an optimal separation of a water distribution network (WDN) into District Metered Areas (DMAs) in order to ensure that the delivered water is of proper age and pressure. At first, the water distribution network is divided into smaller areas via the method of Geometric Partitioning, which is based on Recursive Coordinate Bisection (RCB). Subsequently, Gaussian Mixture Modelling (GMM) solution is applied, obtaining an optimal placement of isolation valves and separation of the WDN into DMAs. The performance of the proposed system is evaluated on two different networks and is compared against the Genetic Algorithm (GA) tool, constituting a very promising approach, especially for sizeable water distribution networks due to the diminished running time and the noteworthy reduction of pressure and water age.

APA, Harvard, Vancouver, ISO, and other styles

34

Ai, Tinghua, and Yingzhe Lei. "Point Label Placement on Hexagonal Map Grids." Abstracts of the ICA 1 (July 15, 2019): 1–2. http://dx.doi.org/10.5194/ica-abs-1-4-2019.

Full text

Abstract:

Abstract. The past few decades have seen the development of automatically feature labelling when manual label placement was thought to be time and labour consuming. Emerging techniques like volunteered geographic information (VGI) collection are making label placement more complexed with many features in a limited space, especially for points of interest (POI). In order to improve the quality and the efficiency of point feature labelling, there have been massive researches focusing on issues like position models, assessment criteria and optimization methods. Most of the researches were using vector-based methods while raster-based methods were less used, because vector-based methods have the advantage of easy definition of features and labels but are usually followed by computation complexity problems for features with high density. In contrast raster-based methods are faster and more flexible, though being harder to represent features and labels precisely on the map grids. Considering that hexagon partitioning was rarely used in raster-based methods, compared with the most commonly used square portioning, and hexagon was potentially useful for its oblique sides and isotropic orientations, hexagonal grids were used in this research to investigate better point feature labelling approaches.A new raster-based method was promoted to figure out high quality label placement of POI in dense area. Labels were placed on a hexagonal map grids based on the principles that one Chinese character is set to one hexagon unit with the mathematical relationship of h&thinsp;=&thinsp;((&radic;3+1)/2)a, while h is the side length of a hexagon unit and a is the size of a Chinese character. Considering that hexagon grids are divided into flat topped type and pointy topped type, which leads to different orientations, split hexagons were promoted to extend orientations from 6 to 8 based on pointy topped grids. A hexagon is partitioned into two parts labelled ‘left’ and ‘right’ and a split hexagon is the combination of a ‘left’ part and a ‘right’ part separately from two neighboring hexagons, as shown in figure 1. Then every hexagon on the grid will have four status: not-occupied {(0,0)}, half-occupied {(0,1) and (1,0)} and both-occupied {(1,1)}. Based on the fundamental concepts above, specific definitions were made on how labels were supposed to be represented on hexagonal map grids, including the length, orientation, writing direction, character orientation and position of the labels.The approach first initially arranges labels of POI with different combinations of label orientations while pursuing coherence as much as possible, including procedures of rasterization of vector data, POI grouping and initial scheme computation. Every POI in a same group would have same label orientation and every POI group may have several accessible orientations thus making initial schemes diverse. Then a second positioning algorithm was conducted to handle overlapping (labels with POI, labels with labels) problems and improve the overall quality of labelling. The algorithm used the methods of position changing and label turning, which allow label to change its position around POI and sometimes change the orientation when it is necessary to avoid collisions. Quality of labels in a closed block was assessed from three aspects: preferential orientation, occlusion and spaciousness. POI data was chosen from restaurant, hotel and shop facilities and figure 2 showed one of the examples of label placement results using this method. The results have shown good orientation consistency of labels and occlusions were reduced to the lowest, though several label-label occlusions remained due to the limited space. After being compared with vector-based method, the approach has shown better performance on maintaining map legibility, aesthetics and harmony.

APA, Harvard, Vancouver, ISO, and other styles

35

Chatzivasili, Stavroula, Katerina Papadimitriou, and Vasilis Kanakoudis. "Optimizing the Formation of DMAs in a Water Distribution Network through Advanced Modelling." Water 11, no. 2 (February 6, 2019): 278. http://dx.doi.org/10.3390/w11020278.

Full text

Abstract:

Water pressure management in a water distribution network (WDN) is a key component applied to achieve desirable water quality as well as a trouble-free operation of the network. This paper presents a hybrid, two-stage approach, to provide optimal separation of a WDN into District Metered Areas (DMAs), improving both water age and pressure. The first stage aims to divide the WDN into smaller areas via the Geometric Partitioning method, which is based on Recursive Coordinate Bisection (RCB). Subsequently, the Student’s t-mixture model (SMM) is applied to each area, providing an optimal placement of isolation valves and separating the network in DMAs. The model is evaluated on a realistic network generated through Watergems and is compared against one variation of it implemented, including the Gaussian Mixture Model (GMM) as well as the Genetic Algorithm (GA) approach, obtaining impressive performance. The implementation of both stages was deployed in a MATLAB environment through the Epanet toolkit. The proposed system is very promising, especially for large size WDNs due to the decreased running time and noteworthy reduction of pressure and water age.

APA, Harvard, Vancouver, ISO, and other styles

36

Megson, G. M. "Systolic partitioning algorithms." Information Processing Letters 46, no. 1 (April 1993): 13–18. http://dx.doi.org/10.1016/0020-0190(93)90189-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Patel, A. M. "Partitioning concepts for placement and applications." Computer-Aided Design 18, no. 7 (September 1986): 395. http://dx.doi.org/10.1016/0010-4485(86)90260-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Jemai, Mehdi, Sonia Dimassi, Bouraoui Ouni, and Abdellatif Mtibaa. "Combined Partitioning Hardware-Software Algorithms." International Journal of Computer Applications 119, no. 4 (June 18, 2015): 11–15. http://dx.doi.org/10.5120/21054-3701.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Fan, Wenfei, Muyang Liu, Chao Tian, Ruiqi Xu, and Jingren Zhou. "Incrementalization of graph partitioning algorithms." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1261–74. http://dx.doi.org/10.14778/3389133.3389142.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Even, Guy, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber. "Fast Approximate Graph Partitioning Algorithms." SIAM Journal on Computing 28, no. 6 (January 1999): 2187–214. http://dx.doi.org/10.1137/s0097539796308217.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Binev, Peter, Albert Cohen, Wolfgang Dahmen, and Ronald DeVore. "Classification algorithms using adaptive partitioning." Annals of Statistics 42, no. 6 (December 2014): 2141–63. http://dx.doi.org/10.1214/14-aos1234.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Kemp, B., S. J. Porter, and J. F. Dawson. "Population partitioning in genetic algorithms." Electronics Letters 34, no. 20 (1998): 1928. http://dx.doi.org/10.1049/el:19981341.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Golovchenko, Evdokiya Nikolayevna. "Survey of graph partitioning algorithms." Keldysh Institute Preprints, no. 2 (2020): 1–38. http://dx.doi.org/10.20948/prepr-2020-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

GREENE, WILLIAM A. "GENETIC ALGORITHMS FOR PARTITIONING SETS." International Journal on Artificial Intelligence Tools 10, no. 01n02 (March 2001): 225–41. http://dx.doi.org/10.1142/s0218213001000490.

Full text

Abstract:

We first revisit a problem from the literature, that of partitioning a given set of numbers into subsets such that their sums are as nearly equal as possible. We devise a new genetic algorithm, Eager Breeder, for this problem. The algorithm is distinctive in its novel and aggressive way of extracting parental genetic material when forming a child partition, and its results are a substantial improvement upon prior results from the literature. Then we extend our algorithm to the more general setting, of partitioning a set in the case that the environment provides us a measure of the fitness of individual subsets in the partition. We apply the extension to two artificial problems, one with a targeted partition whose subsets are of very diverse sizes, and one whose subsets are the same size. Finally, we apply our approach to several map coloring problems, and obtain good results there as well. In our different stages of work, we exploit different heuristics, which are attuned to the particular partitioning problem under attack.

APA, Harvard, Vancouver, ISO, and other styles

45

Iqbal, Mohammad Ashraf. "Approximate algorithms for partitioning problems." International Journal of Parallel Programming 20, no. 5 (October 1991): 341–61. http://dx.doi.org/10.1007/bf01407812.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Park, Taehoon, and Chae Y. Lee. "Algorithms for partitioning a graph." Computers & Industrial Engineering 28, no. 4 (October 1995): 899–909. http://dx.doi.org/10.1016/0360-8352(95)00003-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Lim, Sung Kyu, Ramprasad Ravichandran, and Mike Niemier. "Partitioning and placement for buildable QCA circuits." ACM Journal on Emerging Technologies in Computing Systems 1, no. 1 (March 2005): 50–72. http://dx.doi.org/10.1145/1063803.1063806.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Kirienko, N. A. "Algorithms for partitioning logical circuits into subcircuits." Informatics 17, no. 3 (September 30, 2020): 54–63. http://dx.doi.org/10.37661/1816-0301-2020-17-3-54-63.

Full text

Abstract:

The problem of partitioning a logical circuit into subcircuits is considered. It is of great importance when performing optimization transformations in the process of circuit synthesis. The brief review of partitioning methods and algorithms is given, and two groups of algorithms are identified: constructive and iterative one. The interpretation of a logical circuit in the form of a graph is presented. The problem of partitioning in terms of a graph-theoretic model is defined and some algorithms for solving the partitioning problem are proposed. Logic circuit functions are defined by a system of logical equations. Algorithms perform the partitioning the system of logical equations into subsystems with the restrictions of the number of input and output variables. The data structures to execute the algorithms are defined. Various types of equations connections, obtaining better solutions for partitioning are described. The problems of the use of partitioning algorithms to improve the quality of the circuit at the stage of technology-independent optimization are investigated. The results of an experimental study carried out by the BDD optimization procedure for the functional description of the circuit and LeonardoSpectrum synthesis confirm the effectiveness of the developed algorithms. The algorithms are implemented as partitioning circuit procedures in the experimental FLC system for logical design.

APA, Harvard, Vancouver, ISO, and other styles

49

Arora, Sanjeev, Satish Rao, and Umesh Vazirani. "Geometry, flows, and graph-partitioning algorithms." Communications of the ACM 51, no. 10 (October 2008): 96–105. http://dx.doi.org/10.1145/1400181.1400204.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Guénoche, Alain. "Comparison of algorithms in graph partitioning." RAIRO - Operations Research 42, no. 4 (October 2008): 469–84. http://dx.doi.org/10.1051/ro:2008029.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Partitioning and placement algorithms'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles