For connected handwritten characters, strokes are merged together in the touching area. Artifacts are often present in the separated characters and therefore the recognition performance will deteriorate. The paper des...
详细信息
ISBN:
(纸本)0818685123
For connected handwritten characters, strokes are merged together in the touching area. Artifacts are often present in the separated characters and therefore the recognition performance will deteriorate. The paper describes an approach to find a partitioning path which can reduce the artifacts significantly.
In today’s rapidly evolving cloud computing and IoT landscape, efficiently managing tasks across multiple cloud environments or IoT layers is essential for optimising resource utilisation, monitoring performance requ...
详细信息
ISBN:
(数字)9798350366501
ISBN:
(纸本)9798350366518
In today’s rapidly evolving cloud computing and IoT landscape, efficiently managing tasks across multiple cloud environments or IoT layers is essential for optimising resource utilisation, monitoring performance requirements, and meeting deadlines. To address this challenge, we present a methodology that merges graph partitioning with nested genetic algorithms (GAs) to optimise task allocation while prioritising to meet the deadlines. Our approach focuses on optimising partitions to ensure efficient and secure task execution across multi-cloud environments. Using the inherent structure of task dependencies and resource constraints depicted as a directed graph, we employ graph partitioning techniques to distribute tasks across available cloud or IoT resources while ensuring the task dependencies, thereby minimising makespan, optimising partitions and meeting the timing. To fortify our optimisation framework, various experiments were conducted. The results showcase our approach’s efficacy in achieving superior task scheduling efficiency, reductions in execution times, and optimisation of partitions, all while ensuring the strict timing requirements of critical systems.
This paper initiates a new study on online partitioning algorithms that are sequentially optimized for a query sequence. As queries arrive one at a time, given the option to reconfigure the partition after each query ...
详细信息
ISBN:
(纸本)9781509052530
This paper initiates a new study on online partitioning algorithms that are sequentially optimized for a query sequence. As queries arrive one at a time, given the option to reconfigure the partition after each query so that it can best serve the next query, the objective is to minimize the query read cost and data migration cost. This is an online problem without an optimal solution; online heuristics are the only resort. We investigate this problem by formulating it as a multi-objective optimization and proposing an Evolutionary algorithms (EA) framework incorporating several online heuristics to explore Pareto-optimal solutions. This study is driven by our conjecture that if an online heuristic helps EA converge faster to better partitioning solutions then practically this heuristic should be preferred for adapting the partition to the query sequence.
In this paper, we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s/sub 1/, s/sub 2/, ..., s/sub p/ (such that /spl Sigm...
详细信息
ISBN:
(纸本)0769509878
In this paper, we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s/sub 1/, s/sub 2/, ..., s/sub p/ (such that /spl Sigma//sub i=1//sup p/ s/sub i/=1), so as to minimize (i) either the sum of the p perimeters of the rectangles (ii) or the largest perimeter of the p rectangles. For both problems, we prove NP-completeness and we introduce approximation algorithms.
Mean field annealing (MFA) algorithm, recently proposed for solving combinatorial optimization problems, combines the characteristics of neural networks and simulated annealing. Previous works on MFA resulted with suc...
详细信息
Mean field annealing (MFA) algorithm, recently proposed for solving combinatorial optimization problems, combines the characteristics of neural networks and simulated annealing. Previous works on MFA resulted with successful mapping of the algorithm to some classic optimization problems such as travelling salesman problem and graph partitioning problem. In this paper, MFA is formulated for circuit partitioning problem (CPP) by using both graph and network models. Initial results of the implementations show that MFA can be used as an efficient alternative heuristic for CPP. MFA algorithms proposed for solving CPP are parallelized and implemented on an iPSC/2 hypercube multicomputer. Experimental results show that the proposed heuristics can be efficiently parallelized on hypercube multicomputers, which is crucial for algorithms solving such computationally hard problems.< >
We present efficient parallel algorithms for some geometric bipartitioning problems. Our algorithms are designed to run in the CREW PRAM model of parallel computation. These bipartition problems are the following. Giv...
详细信息
We present efficient parallel algorithms for some geometric bipartitioning problems. Our algorithms are designed to run in the CREW PRAM model of parallel computation. These bipartition problems are the following. Given a planar point set S (left| S right| = n), a measure mu acting on S and a pair of values fmu_1 and mu_2, does there exist a bipartition S = S_1 cup S_2 such that mu(S_{1}) leqslant mu_i for i = 1,2? We present efficient parallel algorithms for several measures like diameter under L_infty and L_1 metric; area, perimeter or length of diagonal of the smallest enclosing axes-parallel rectangle and the side length of the smallest enclosing axes-parallel square. All our parallel algorithms run in O(logn) time using O{n) processors in the CREW PRAM. The work done (processor-time product) by our algorithms matches the time complexity of the best known sequential algorithms for most of these problems. As a by product of our algorithms, we can perform report mode orthogonal range queries in optimal O(logn) time using 0(1 + k/logn) processors, where k is the number of points inside the query range. The processor-time product for this range reporting algorithm is optimal.
Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem)...
详细信息
Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem) for disjoint (disjoint serial) decomposition, such that the decomposed circuits are smaller in size and its truth table representation have maximal don't cares. A novel pruned breadth first search (PBFS/IPBFS) approach is proposed to determine the set of good variable partitions with minimal time and computational complexity. The heuristics proposed minimize the size of the sub functions. The proposed approach has been successfully implemented and test with MCNC and Espresso benchmarks.
Unmanned Aerial Vehicles (UAVs) have emerged as one of the most researched topics in recent times. They are being deployed in ample applications without any human intervention. The use of autonomous UAVs has given ris...
详细信息
ISBN:
(纸本)9781728158754;9781728192994
Unmanned Aerial Vehicles (UAVs) have emerged as one of the most researched topics in recent times. They are being deployed in ample applications without any human intervention. The use of autonomous UAVs has given rise to many new challenges. Path planning has always been one of the most critical problems when it comes to the deployment of UAVs in real-time applications. The current work focuses on the area partitioning algorithm considering a few significant parameters such as static obstacles and altitude of UAVs. For any given geographic area, the proposed area partitioning algorithm finds a division of the entire area of interest by effectively partitioning into rectangles. The algorithm merges two or more equal-sized rectangles based on the obstacle position, resulting in a rectilinear partitioning of the area. Two mid-points are computed for each partition and are further used for the computation of an optimal path. An optimal path for the UAV is found by constructing a graph from the mid-points, posing the problem as Travelling Salesperson Problem(TSP), and finding a solution using Firefly Algorithm(FA) and Particle Swarm Optimization(PSO). Effective comparison is done to find the optimal path using both techniques. The obtained results show that FA outperforms PSO.
One of the most important and difficult tasks in multi-FPGA systems design is partitioning. The main problems are related to the I/O pins and logic capacity of FPGAs. The number of pins available is a critical problem...
详细信息
One of the most important and difficult tasks in multi-FPGA systems design is partitioning. The main problems are related to the I/O pins and logic capacity of FPGAs. The number of pins available is a critical problem, because FPGA devices have such a reduced number of them compared with their logic capacity. In addition we must reserve some of the pins to interconnect parts of the circuit placed on non-adjacent FPGAs. Most of the previous works have been adapted from other VLSI areas, and hence, they disregard the specific features of these kind of circuit. A new method for solving the partitioning and placement problem in multi-FPGA systems is presented. We use graph theory to describe the circuit, then a classical genetic algorithm (GA) is applied with a problem-specific encoding. The algorithm preserves the original structure of the circuit and by means of a fuzzy technique it evaluates the I/O-pins consumption due to direct and indirect connections between FPGAs. We have used the partitioning93 benchmarks described with the Xilinx Netlist Format (XNF). The results obtained show how genetic algorithms are capable of accomplishing successfully the partitioning and placement tasks while respecting the board constraints.
Results are presented on the effectiveness of several algorithms for partitioning graphs with weighted nodes and edges. Such graphs can represent a number of interesting program structures, such as processes using mes...
详细信息
Results are presented on the effectiveness of several algorithms for partitioning graphs with weighted nodes and edges. Such graphs can represent a number of interesting program structures, such as processes using message passing or dataflow graphs and other distributed software. The graph partitions can be used in software tools to control the allocation of program units to distributed processes in ways which minimize communication cost, completion time or utilization. It is shown that, in situations in which a good partition is crucial, simulated annealing is the most effective algorithm. It is, however, an expensive algorithm to run, and when this is important good results can still be obtained by using a variant of a greedy algorithm. A number of other algorithms that can be useful in particular situations are described. Those can be of practical use to distributed system designers.< >
暂无评论