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

5th International Symposium on Graph Drawing, GD 1997

作者： Fekete, Sándor P. Houle, Michael E. Whitesides, Sue Center for Parallel Computing Universität zu Köln KölnD-50923 Germany Department of Computer Science University of Newcastlc CallaghanNSW2308 Australia School of Computer Science McGill University 3480 University St. #318 MontréalQuébec Canada

ISBN: (纸本)9783540639381

The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which subgraphs exist for which the only possible layouts are rigid. In this paper we introduce an extension called the wobbly logic engine which can be used to prove the NP-hardness of several graph representations for which no such rigid layouts exist, representations by visibility and intersection in particular. We illustrate the method by using the wobbly technique to show the NP-hardness of deciding whether a graph has a nondegenerate z-axis parallel visibility representation (ZPR) by unit squares. © Springer-Verlag Berlin Heidelberg 1997.

关键词： Visibility

来源：评论

学校读者我要写书评

暂无评论

Scalable quantum detector tomography by high-performance computing

arXiv

引用

arXiv 2024年

作者： Schapeler, Timon Schade, Robert Lass, Michael Plessl, Christian Bartley, Tim J. Department of Physics Paderborn University Warburger Str. 100 Paderborn33098 Germany Paderborn University Warburger Str. 100 Paderborn33098 Germany Paderborn Center for Parallel Computing Paderborn University Warburger Str. 100 Paderborn33098 Germany Department for Computer Science Paderborn University Warburger Str. 100 Paderborn33098 Germany

At large scales, quantum systems may become advantageous over their classical counterparts at performing certain tasks. Developing tools to analyse these systems at the relevant scales, in a manner consistent with quantum mechanics, is therefore critical to benchmarking performance and characterising their operation. While classical computational approaches cannot perform like-for-like computations of quantum systems beyond a certain scale, classical high-performance computing (HPC) may nevertheless be useful for precisely these characterisation and certification tasks. By developing open-source customised algorithms using high-performance computing, we perform quantum tomography on a megascale quantum photonic detector covering a Hilbert space of 106. This requires finding 108 elements of the matrix corresponding to the positive operator valued measure (POVM), the quantum description of the detector, and is achieved in minutes of computation time. Moreover, by exploiting the structure of the problem, we achieve highly efficient parallel scaling, paving the way for quantum objects up to a system size of 1012 elements to be reconstructed using this method. In general, this shows that a consistent quantum mechanical description of quantum phenomena is applicable at everyday scales. More concretely, this enables the reconstruction of large-scale quantum sources, processes and detectors used in computation and sampling tasks, which may be necessary to prove their nonclassical character or quantum computational advantage. Copyright © 2024, The Authors. All rights reserved.

关键词： Tomography

来源：评论

学校读者我要写书评

暂无评论

A network-flow technique for finding low-weight bounded-degree spanning trees 5th

A network-flow technique for finding low-weight bounded-degr...

引用

5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996

作者： Fekete, Sándor P. Khuller, Samir Klemmstein, Monika Raghavachari, Balaji Young, Neal Center for Parallel Computing Universität zu Köln KölnD-50923 Germany Computer Science Department and Institute for Advanced Computer Studies University of Maryland College ParkMD20742 United States Department of Computer Science The University of Texas at Dallas Box 830688 RichardsonTX75083-0688 United States Department of Computer Science Dartmouth College HanoverNH03755-3510 United States

ISBN: (纸本)3540613102

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning tree T using adoptions to meet the degree constraints is considered. A novel network-flow based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previously obtained. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for any algorithm at all, then it also holds for our algorithm. The performance guarantee is the *** the degree constraint d(v) for each v is at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times (formula presented) where degT(v) is the initial degree of v. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. Choosing T to be a minimum spanning tree yields approximation algorithms for the general problem on geometric graphs with distances induced by various Lp norms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2. © Springer-Verlag Berlin Heidelberg 1996.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The virtual resource manager: an architecture for SLA-aware resource management 04

The virtual resource manager: an architecture for SLA-aware ...

引用

IEEE/ACM International Symposium on Cluster computing and the Grid (CCGRID)

作者： L.-O. Burchard M. Hovestadt O. Kao A. Keller B. Linnert Faculty of Computer Science and Electrical Engineering Technische Universität Berlin Germany Paderbom Center of Parallel Computing (PC2) Universitat Paderborn Germany

ISBN: (纸本)9780780384309

The next generation Grid will demand the Grid middleware to provide flexibility, transparency, and reliability. This implies the appliance of service level agreements to guarantee a negotiated level of quality of service. These requirements also affect the local resource management systems providing resources for the Grid. At this a gap between these demands and the features of today's resource management systems becomes apparent. In this paper we present an approach which closes this gap. Introducing the architecture of the virtual resource manager we highlight its main features of runtime responsibility, resource virtualization, information hiding, autonomy provision, and smooth integration of existing resource management system installations.

关键词： Resource management computer architecture Middleware Grid computing Resource virtualization Quality of service computer network management computer science parallel processing Home appliances

来源：评论

学校读者我要写书评

暂无评论

Cost-optimal parallel algorithms for traversing trees

Cost-optimal parallel algorithms for traversing trees

引用

IEEE Southeastcon

作者： S.K. Das C.C.-Y. Chen Center of Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX USA

The authors present cost-optimal parallel algorithms for depth-order (e.g., pre-, in-, and post-order) and level-order (e.g., breadth-first and breadth-depth) traversals of general trees with n nodes. Each of the algo... 详细信息

关键词： parallel algorithms Phase change random access memory computer science Binary trees Distributed computing Classification tree analysis Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

Cost-optimal parallel algorithms for finitely inductive sequences

Cost-optimal parallel algorithms for finitely inductive sequ...

引用

Annual Hawaii International Conference on System sciences (HICSS)

作者： S.K. Das P.S. Fisher H. Zhang Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX USA

Finitely inductive (FI) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. The authors propose cost-optimal parallel algorithms for FI sequence processing. These algorithms include parallel factoring and following by bucket packing and by hashing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. Each of the algorithms achieves cost-optimal speedup under certain conditions as detailed.< >

关键词： parallel algorithms Pattern recognition Pattern matching Distributed computing computer science Impedance matching Phase change random access memory Multiple signal classification Signal detection Motion detection

来源：评论

学校读者我要写书评

暂无评论

Dynamic load balancing strategies for conservative parallel simulations

Dynamic load balancing strategies for conservative parallel ...

引用

Workshop on Principles of Advanced and Distributed Simulation (PADS)

作者： A. Boukerche S.K. Das Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX USA

This paper studies the problem of load balancing for conservative parallel simulations for execution on a multicomputer. The synchronization protocol makes use of Chandy-Misra (1979) null-messages. We propose a dynamic load balancing algorithm which assumes no compile time knowledge about the workload parameters. It is based upon a process migration mechanism, and the notion of CPU-queue length, which indicates the workload at each processor. We examine two variations for the algorithm which we refer to as centralized and multi-level hierarchical methods, in the context of queueing network simulation of a torus. The torus was chosen because its many cycles aid in the formation of deadlock, making it a stress test for any conservative synchronization protocols. Our experiments indicate that our dynamic load balancing schemes significantly reduce the run time of an optimized version of Chandy-Misra null message approach, and decreases by 30-40% the synchronization overhead when compared to the use of a static partitioning algorithm. Significantly, the results obtained also indicate that the multi-level scheme always outperforms both the centralized load balancing approach and the static partitioning algorithm.

关键词： Load management Computational modeling Protocols Distributed computing Stress Testing Partitioning algorithms Discrete event simulation computer simulation Concurrent computing

来源：评论

学校读者我要写书评

暂无评论

The canonical amoebot model: Algorithms and concurrency control 35

The canonical amoebot model: Algorithms and concurrency cont...

引用

35th International Symposium on Distributed computing, DISC 2021

作者： Daymude, Joshua J. Richa, Andréa W. Scheideler, Christian Biodesign Center for Biocomputing Security and Society Arizona State University TempeAZ United States School of Computing and Augmented Intelligence Arizona State University TempeAZ United States Department of Computer Science Universität Paderborn Germany

ISBN: (纸本)9783959772105

The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems;however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter. © Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler;licensed under Creative Commons License CC-BY 4.0

关键词： Concurrency control

来源：评论

学校读者我要写书评

暂无评论

Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems 1

Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memor...

引用

1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022

ISBN: (纸本)9783959772242

Mutual exclusion is a classical problem in distributed computing that provides isolation among concurrent action executions that may require access to the same shared resources. Inspired by algorithmic research on distributed systems of weakly capable entities whose connections change over time, we address the local mutual exclusion problem that tasks each node with acquiring exclusive locks for itself and the maximal subset of its "persistent" neighbors that remain connected to it over the time interval of the lock request. Using the established time-varying graphs model to capture adversarial topological changes, we propose and rigorously analyze a local mutual exclusion algorithm for nodes that are anonymous and communicate via asynchronous message passing. The algorithm satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. It requires O(∆) memory per node and messages of size Θ(1), where ∆ is the maximum number of connections per node. We conclude by describing how our algorithm can implement the pairwise interactions assumed by population protocols and the concurrency control operations assumed by the canonical amoebot model, demonstrating its utility in both passively and actively dynamic distributed systems. © Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler;licensed under Creative Commons License CC-BY 4.0

关键词： Locks (fasteners)

来源：评论

学校读者我要写书评

暂无评论

Development Progress of SWLBM a Framework Based on Lattice Boltzmann Method for Fluid Dynamics Simulation 1

引用

18th International Symposium on Applied Reconfigurable computing, ARC 2022

作者： Xuesen, Chu Xiang, He Fang, Li Zhao, Liu Guangwen, Yang Department of Computer Science and Technology Tsinghua University Beijing100084 China China Ship Scientific Research Center Wuxi214082 China Taihu Laboratory of DeepSea Technological Science Wuxi214082 China Jiangnan Institute of Computing Technology Wuxi214083 China National Research Center of Parallel Computer Engineering and Technology Beijing100084 China National Supercomputing Center in Wuxi Wuxi214072 China

ISBN: (数字)9783031199837

ISBN: (纸本)9783031199820

SWLBM is a software framework based on Lattice Boltzmann Method (LBM) for Computational Fluid Dynamic (CFD) running on Sunway many-core processors. In this paper, we review the achievements of code developing in early stage and introduce the development progress recently of this software, including the development of parallel optimization for Sunway new-generation supercomputing system, functional extensions of the software like pre-process function for mesh generation from a geometry file with STL file and BMP file, Immersed boundary condition for moving subject simulation. Some applications with SWLBM will be introduced to show the advantage of this software over other CFD code in large-scale simulations. SWLBM is still under development, with the continuous improvement of functions, it will play a greater role in the field of fluid simulation. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Computational fluid dynamics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：