检索结果-内蒙古大学图书馆

ON NETWORK partitioning ALGORITHM OF LARGE-SCALE CMOS CIRCUITS

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS 1989年第2期36卷 294-299页

作者： DENG, AC Department of Electrical Engineering Texas A and M University College Station TX USA

A topological partitioning algorithm which decouples the large-scale CMOS circuits into numerous small-scale subcircuits, in which each subcircuit can be individually analyzed with better overall efficiency, is discussed. The parasitic couplings between the partitioned subcircuits are shown to be negligible in most digital circuits. Bidirectional coupling between cross-coupled subcircuits is studied and a decoupling criterion is derived. The flexibility offered by the decoupled structure can be fully taken advantage of by using: (1) the latency; (2) the event-driven operation; and (3) the regular structure of the partitioned subcircuits. An experimental program, as a result from the partitioning algorithm, demonstrates a three-order-of-magnitude speed improvement over the SPICE program.< >

关键词： partitioning algorithms Large-scale systems Coupling circuits Algorithm design and analysis Digital circuits Delay SPICE

来源：评论

学校读者我要写书评

暂无评论

Group Reassignment for Dynamic Edge partitioning

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2021年第10期32卷 2477-2490页

作者： Li, He Yuan, Hang Huang, Jianbin Cui, Jiangtao Ma, Xiaoke Wang, Senzhang Yoo, Jaesoo Yu, Philip S. Xidian Univ Sch Comp Sci & Technol Xian 710126 Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Chungbuk Natl Univ Dept Informat & Commun Engn Cheongju 361763 South Korea Univ Illinois Chicago IL 60607 USA Tsinghua Univ Inst Data Sci Beijing 100083 Peoples R China

Graph partitioning is a mandatory step in large-scale distributed graph processing. When partitioning real-world power-law graphs, the edge partitioning algorithm performs better than the traditional vertex partitioning algorithm, because it can cut a single vertex into multiple replicas to apportion the computation. Many advanced edge partitioning methods are designed for partitioning a static graph from scratch. However, the real-world graph structure changes continuously, which leads to a decrease in partition quality and affects the performance of the graph applications. Some studies are devoted to offline repartitioning or batch incremental partitioning, but how to deal with dynamics in real-time is still worthy of in-depth study. In this article, we discuss the impact of dynamic change on partition and discover that both insertion and deletion will lead to local suboptimal partitioning, which is the reason for the degradation of partition quality. As a solution, a dynamic edge partitioning algorithm is proposed to partition dynamics in real-time. Specifically, we deal with dynamics by a distributed stream and improve partition quality by reassigning some closely connected edges. Experiments show that it is robust to initial partition quality, dynamic scale and type, and distributed scale. Compared with the state-of-the-art dynamic partitioner, it can reduce vertex-cuts by 29.5 percent. Compared with the repartitioning algorithms, it can save the partitioning time by 91.0 percent. Applied on the graph task, it can reduce the increase of communication cost and the increase of the total time of task by 41.5 and 71.4 percent.

关键词： Heuristic algorithms partitioning algorithms Real-time systems Task analysis Electronic mail Aerodynamics Social networking (online) Dynamic graph edge partitioning distributed system edge group

来源：评论

学校读者我要写书评

暂无评论

High-Quality Shared-Memory Graph partitioning

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第11期31卷 2710-2722页

作者： Akhremtsev, Yaroslav Sanders, Peter Schulz, Christian Google Zurich Switzerland Karlsruhe Inst Technol KIT D-76131 Karlsruhe Germany Univ Vienna Fac Comp Sci A-1010 Vienna Austria

partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation in processing graphs. Recently, size, variety, and structural complexity of these networks has grown dramatically. Unfortunately, previous approaches to parallel graph partitioning have problems in this context since they often show a negative trade-off between speed and quality. We present an approach to multi-level shared-memory parallel graph partitioning that produces balanced solutions, shows high speedups for a variety of large graphs and yields very good quality independently of the number of cores used. For example, in an extensive experimental study, at 79 cores, one of our closest competitors is faster but fails to meet the balance criterion in the majority of cases and another is mostly slower and incurs about 13 percent larger cut size. Important ingredients include parallel label propagation for both coarsening and refinement, parallel initial partitioning, a simple yet effective approach to parallel localized local search, and fast locality preserving hash tables.

关键词： partitioning algorithms Clustering algorithms Program processors Complex networks Contracts Parallel algorithms Parallel graph partitioning shared-memory parallelism local search label propagation

来源：评论

学校读者我要写书评

暂无评论

A performance-driven logic emulation system: FPGA network design and performance-driven partitioning

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1996年第5期15卷 560-568页

作者： Kim, CH Shin, HC Department of Electronics Engineering Han Yang University South Korea

FPGA's are widely used for logic emulation, software acceleration, custom computing, and prototyping. The architecture (or the interconnect mechanism of a FPGA network) of an emulator has pro-found effect on the performance (speed) and efficiency (chip utilization) of the emulator. In this paper, several architectures of FPGA networks are suggested, and they are compared with other typical existing architectures by using the MCNC partition benchmark circuits. Experimental results show that tripartite network outperforms six other typical architectures both in performance and in efficiency. For this study, the propagation delay of a path is estimated bt the number of hops (interchip connections) and the number of intrachip connections on the path, and thus it is independent of a specific FPGA type. To partition a given circuit into the given prerouted network of FPGA's, a new routability-driven partitioning algorithm is developed, Experimental results using the MCNC benchmark examples show that our partition method produces better results than those of other recent approaches on the average, and that performance-driven partitioning is effective in reducing critical time delays.

关键词： Logic design Emulation Field programmable gate arrays Computer architecture Acceleration Software prototyping Integrated circuit interconnections Propagation delay Delay estimation partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

Spectral-based multiway FPGA partitioning

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1996年第5期15卷 554-560页

作者： Chan, PK Schlag, MDF Zien, JY Computer Engineering Board University of California Santa Cruz CA USA

Recent research on FPGA partitioning has focused on finding minimum cuts between partitions without regard to the routability of the partitioned subcircuits. In this paper, we develop a spectral approach to multiway partitioning in which the primary goal is to produce routable subcircuits while maximizing FPGA device utilization. To assist the partitioner in assessing the routability of the partitioned subcircuits, we have developed a theory to predict the routability of the partitioned subcircuits prior to partitioning. Advancement over previous work is evidenced by results of experiments on standard MCNC benchmarks.

关键词： Field programmable gate arrays partitioning algorithms Routing Cost function Emulation Constraint theory Logic Integrated circuit yield Design automation

来源：评论

学校读者我要写书评

暂无评论

LOCAL RATIO CUT AND SET COVERING partitioning FOR HUGE LOGIC EMULATION SYSTEMS

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1995年第9期14卷 1085-1092页

作者： CHOU, NC LIU, LT CHENG, CK DAI, WJ LINDELOF, R AT&T BELL LABS MURRAY HILLNJ 07974 UNIV CALIF SAN DIEGO DEPT COMP SCI & ENGNLA JOLLACA 92093

Given a system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGA's for logic emulation. We first devise a Local Ratiocut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed as an alternative to the widely adopted recursive partitioning paradigm. Experimental results have shown that our approach achieved significant improvement with much shorter run times compared to the recursive Fiduccia-Mattheyses approach on large designs. For instance, on a benchmark of 160K gates and 90K nets, we reduced the number of FPGA's required and the run time by 41 and 86%, respectively.

关键词： Emulation partitioning algorithms Logic design Logic circuits Clustering algorithms Algorithm design and analysis Complexity theory Design methodology Hardware Fabrication

来源：评论

学校读者我要写书评

暂无评论

Network Aware Mobile Edge Computation partitioning in Multi-User Environments

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2021年第5期14卷 1478-1491页

作者： Yang, Lei Cao, Jiannong Wang, Zhenyu Wu, Weigang South China Univ Technol Sch Software Engn Guangzhou 510630 Guangdong Peoples R China Hong Kong Polytech Univ Dept Comp Hung Hom Hong Kong Peoples R China Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510275 Peoples R China

Mobile edge computation partitioning is an effective technique to improve the applications performance on the mobile devices by selectively offloading some computations from the devices to the nearby edge cloud. Most previous works focus on the computation partitioning for a single user. Recent works begin to study the computation partitioning in a multiple user environment in which a number of users compete for the constrained computation resources on the edge cloud. However, these works neglect the fact that the users normally also share the network resources to access the edge cloud, and thus the allocation of bandwidth to the users significantly affects the overall performance of the users. In this paper, we study network aware mobile edge computation partitioning in multi-user environments, i.e., to decide for each user which parts of the application should be offloaded onto the edge cloud, and which others should be executed locally, and meanwhile to allocate the access bandwidth among the users, such that the average application performance of the users is maximized. This problem is new in that we consider the competition among users for the network bandwidth as well as the computation resources in a multi-user environment. With a set of novel models and formulations, we transform the problem into the classic Multi-class Multi-dimensional Knapsack Problem, and develop an effective algorithm, namely Performance Function Matrix based Heuristic (PFM-H), to solve it. We further consider the user mobility and design effective online algorithms that could be easily deployed in practical systems. Comprehensive trace driven simulations show that our proposed algorithm outperforms the benchmark algorithms significantly in the average application performance.

关键词： Bandwidth Cloud computing Throughput Mobile handsets Heuristic algorithms Computational modeling partitioning algorithms Mobile edge computing computation partitioning resource allocation

来源：评论

学校读者我要写书评

暂无评论

partitioning Models for General Medium-Grain Parallel Sparse Tensor Decomposition

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2021年第1期32卷 147-159页

作者： Karsavuran, M. Ozan Acer, Seher Aykanat, Cevdet Bilkent Univ Comp Engn Dept TR-06800 Ankara Turkey Sandia Natl Labs Ctr Comp Res Albuquerque NM 87123 USA

The focus of this article is efficient parallelization of the canonical polyadic decomposition algorithm utilizing the alternating least squares method for sparse tensors on distributed-memory architectures. We propose a hypergraph model for general medium-grain partitioning which does not enforce any topological constraint on the partitioning. The proposed model is based on splitting the given tensor into nonzero-disjoint component tensors. Then a mode-dependent coarse-grain hypergraph is constructed for each component tensor. A net amalgamation operation is proposed to form a composite medium-grain hypergraph from these mode-dependent coarse-grain hypergraphs to correctly encapsulate the minimization of the communication volume. We propose a heuristic which splits the nonzeros of dense slices to obtain sparse slices in component tensors. So we partially attain slice coherency at (sub)slice level since partitioning is performed on (sub)slices instead of individual nonzeros. We also utilize the well-known recursive-bipartitioning framework to improve the quality of the splitting heuristic. Finally, we propose a medium-grain tripartite graph model with the aim of a faster partitioning at the expense of increasing the total communication volume. Parallel experiments conducted on 10 real-world tensors on up to 1024 processors confirm the validity of the proposed hypergraph and graph models.

关键词： Tensile stress Program processors partitioning algorithms Computational modeling Sparse matrices Load modeling Minimization sparse tensor tensor decomposition canonical polyadic decomposition communication cost communication volume medium-grain partitioning recursive bipartitioning hypergraph partitioning graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Application of an Efficient Graph-Based partitioning Algorithm for Extended Target Tracking Using GM-PHD Filter

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2020年第6期56卷 4451-4466页

作者： Qin, Zheng Kirubarajan, Thia Liang, Yangang Natl Univ Def Technol Coll Aerosp Sci & Engn Changsha 410073 Peoples R China McMaster Univ Dept Elect & Comp Engn Hamilton ON L8S 4L8 Canada

One of the main tasks involving the extended target tracking is howto partition the measurement set accurately and efficiently. In this article, an efficient graph-based partitioning algorithm is introduced for extended target tracking. To reduce the computational load and the interference of clutter on the measurement set partition, a measurement set preprocessing method based on density-based clustering algorithm is presented. An intuitive directed k-nearest neighbor (kNN) graph model based on graph theory is established to represent the relationship between different measurements in the measurement set that needs to be segmented. In the framework of directed kNN graph, a novel similarity metric based on shared nearest neighbor (SNN) is used, and a pairwise similarity that integrates the number of elements in the set of SNN and the closeness of data points is constructed. The spectral clustering algorithm is used to process the multiway cut in the directed kNN graph. The graph-based partitioning algorithm is applied to the extended target Gaussian mixture probability hypothesis density filter. Simulation results illustrate the advantages of our proposed graph-based partitioning algorithm in performance and computational efficiency.

关键词： partitioning algorithms Target tracking Clustering algorithms Density measurement Clutter Computational modeling Time measurement Density-based spatial clustering of applications with noise (DBSCAN) extended target tracking Gaussian mixture probability hypothesis density (GM-PHD) graph theory spectral clustering

来源：评论

学校读者我要写书评

暂无评论

3D Surface-Closed Mesh Clipping Based on Polygonal partitioning for Surgical Planning

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2024年第7期30卷 3374-3385页

作者： Gong, Mingjun Chen, Xiaojun Shanghai Jiao Tong Univ Sch Mech Engn Inst Biomed Mfg & Life Qual Engn Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Sch Mech Engn Inst Med Robot Shanghai 200240 Peoples R China

How to create an efficient and accurate interactive tool for triangular mesh clipping is one of the key problems to be solved in computer-assisted surgical planning. Although the existing algorithms can realize three-dimensional model clipping, problems still remain unsolved regarding the flexibility of clipping paths and the capping of clipped cross-sections. In this study, we propose a mesh clipping algorithm for surgical planning based on polygonal convex partitioning. First, two-dimensional polygonal regions are extended to three-dimensional clipping paths generated from selected reference points. Second, the convex regions are partitioned with a recursive algorithm to obtain the clipped and residual models with closed surfaces. Finally, surgical planning software with the function of mesh clipping has been developed, which is capable to create complex clipping paths by normal vector adjustment and thickness control. The robustness and efficiency of our algorithm have been demonstrated by surgical planning of craniomaxillofacial osteotomy, pelvis tumor resection and cranial vault remodeling.

关键词： Surgery Planning partitioning algorithms Computational modeling Three-dimensional displays Software algorithms Software Model clipping surgical planning triangular mesh partitioning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：