Summary form only given. We describe an algorithm for partitioning 2-weighted geometric graphs, so that each of the two weights is evenly distributed among all partitions and cutsize is minimal. This algorithm is appl...
详细信息
Summary form only given. We describe an algorithm for partitioning 2-weighted geometric graphs, so that each of the two weights is evenly distributed among all partitions and cutsize is minimal. This algorithm is applicable to load balancing problems in parallel computing, including scientific computation or circuit optimization, in which computational load depends on multiple factors, and geometric proximity needs to be preserved. We first show that for two continuous weight distributions, there always exists an L-shape separator that divides the two weights exactly. Based on this fact, we then give a practical and efficient heuristic for 2/sup p/-way partitioning. Our heuristic relies on recursive bipartitioning and runs in O(nlgn+m2/sup p/) time, where n is the number of vertices and m is the number of rows in the graph. In experiments with geometric graphs obtained from placed benchmark VLSI circuits, our heuristic generates balanced partitions with imbalance no greater than 2%, very short runtimes, and good cutsizes. For example, given a geometric graph with n>100,000, our heuristic computes a 32-way partitioning with 0.46% maximum imbalance within 0.5 second.
This paper is devoted to the study of the static and dynamical behaviour of a ID torsion single crystal silicon micro-mirror. The aim is to create a parametric model of such mirror allowing to use a simple calculation...
详细信息
This paper is devoted to the study of the static and dynamical behaviour of a ID torsion single crystal silicon micro-mirror. The aim is to create a parametric model of such mirror allowing to use a simple calculation program to avoid expensive and long FEM simulations. This study tries to put in place a modelling to define the best structure with regard to various specification by taking into account the technological possibilities and to simulate the experimental characteristics before the expensive technological process.
暂无评论