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

Re-evaluating scaling methods for distributed parallel systems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Végh, János Kalimános BT Debrecen4032 Hungary

The paper explains why Amdahl’s Law shall be interpreted specifically for distributed parallel systems and why it generated so many debates, discussions, and abuses. We set up a general model and list many of the terms affecting parallel processing. We scrutinize the validity of neglecting certain terms in different approximations, with special emphasis on the famous scaling laws of parallel processing. We clarify that when using the right interpretation of terms, Amdahl’s Law is the governing law of all kinds of parallel processing. Amdahl’s Law describes among others the history of supercomputing, the inherent performance limitation of the different kinds of parallel processing and it is the basic Law of the’modern computing’ paradigm, that the computing systems working under extreme computing conditions are desperately needed. Copyright © 2020, The Authors. All rights reserved.

关键词： parallel processing systems

Log diameter rounds algorithms for 2-vertex and 2-edge connectivity 46

学校读者我要写书评

暂无评论

Log diameter rounds algorithms for 2-vertex and 2-edge conne...

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

作者： Andoni, Alexandr Stein, Clifford Zhong, Peilin Columbia University New York CityNY United States

ISBN: (纸本)9783959771092

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data - data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. In this paper, we study two fundamental problems, 2-edge connectivity and 2-vertex connectivity (biconnectivity). PRAM algorithms which run in O(log n) time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an n-vertex, m-edge graph of diameter D and bi-diameter D0, 1) a O(log D log logm/n n) parallel time 2-edge connectivity algorithm, 2) a O(log D log2 logm/n n + log D0 log logm/n n) parallel time biconnectivity algorithm, where the bi-diameter D0 is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be O(nδ) for arbitrary constant δ > 0, and the total memory used is linear in the problem size. Our 2-edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of [4]. We also show an Ω(log D0) conditional lower bound for the biconnectivity problem. © Alexandr Andoni, Clifford Stein, and Peilin Zhong;licensed under Creative Commons License CC-BY

关键词： parallel processing systems

The mean-field behavior of processor sharing systems with general job lengths under the SQ(d) policy 36

学校读者我要写书评

暂无评论

The mean-field behavior of processor sharing systems with ge...

36th IFIP Performance Conference 2018

作者： Vasantam, Thirupathaiah Mukhopadhyay, Arpan Mazumdar, Ravi R. Department of ECE University of Waterloo Waterloo Canada INFCOM LCA2 EPFL Lausanne Switzerland

In this paper, we derive the mean-field behavior of empirical distributions of large systems that consist of N (large) identical parallel processor sharing servers with Poisson arrival process having intensity Nλ and generally distributed job lengths under the randomized SQ(d) load balancing policy. Under this policy, an arrival is routed to the server with the least number of progressing jobs among d randomly chosen servers. The mean-field is then used to approximate the statistical properties of the system. In particular, we show that in the limit as N grows, individual servers are statistically independent of others (propagation of chaos) and more importantly, the equilibrium point of the mean-field is insensitive to the job length distributions. This has important engineering relevance for the robustness of such routing policies that are often used in web server farms. We use a measure-valued process approach and martingale techniques to obtain our results. We also provide numerical results to support our analysis. © is is held held by by author/owner(s). author/owner(s).

关键词： parallel processing systems

Hardware-irrelevant parallel processing system

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Zou, Xiuting Xu, Shaofu Deng, Anyi Wang, Rui Zou, Weiwen Department of Electronic Engineering Shanghai Jiao Tong University Shanghai200240 China

parallel processing technology has been a primary tool for achieving high-speed, high-accuracy, and broadband processing for many years across modern information systems and data processing such as optical and radar, synthetic aperture radar imaging, digital beam forming, and digital filtering systems. However, hardware deviations in a parallel processing system (PPS) severely degrade system performance and pose an urgent challenge. We propose a hardware-irrelevant PPS of which the performance is unaffected by hardware deviations. In this system, an embedded convolutional recurrent autoencoder (CRAE), which learns inherent system patterns as well as acquires and removes adverse effects brought by hardware deviations, is adopted. We implement a hardware-irrelevant PPS into a parallel photonic sampling system to accomplish a high-performance analog-to-digital conversion for microwave signals with high frequency and broad bandwidth. Under one system state, a category of signals with two different mismatch degrees is utilized to train the CRAE, which can then compensate for mismatches in various categories of signals with multiple mismatch degrees under random system states. Our approach is extensively applicable to achieving hardware-irrelevant PPSs which are either discrete or integrated in photonic, electric, and other fields. Copyright © 2020, The Authors. All rights reserved.

关键词： parallel processing systems

Constantly wide tree for parallel processing 4

学校读者我要写书评

暂无评论

Constantly wide tree for parallel processing

4th All-Russian Scientific and Practical Conference with International Participation "Information systems and Technologies in Modeling and Control", ISTMC 2019

作者： Shevskiy, Vladislav Saint Petersburg Electrotechnical University "LETI" Saint Petersburg197376 Russia

Improving the performance of modern computing devices requires the adaptation of data processing algorithms for the efficient use of hardware resources. This article provides comparisons of existing database management systems and shows their disadvantages when used in conjunction with parallel processing algorithms. An approach to data storage is presented that can be used to optimize the execution of database queries using parallel processing. A method for constructing the proposed data structuring storage algorithm is described. At the same time, the advantages of the algorithm and the ways of interaction with it to achieve greater benefits in comparison with the existing analogs are shown. Copyright 2019 for this paper by its authors.

关键词： parallel processing systems

Fair and adequate explanations

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Asher, Nicholas Paul, Soumya Russell, Chris Irit Université Paul Sabatier 118 route de Narbonne Toulouse31062 France Telindus 18 rue du Puits Romain BertrangeL-8070 Luxembourg Amazon Research Tübingen Germany

Recent efforts have uncovered various methods for providing explanations that can help interpret the behavior of machine learning programs. Exact explanations with a rigorous logical foundation provide valid and complete explanations, but they have an epistemological problem: they may be too complex for humans to understand and too expensive to compute even with automated reasoning methods. Interpretability requires good explanations that humans can grasp and can compute. We take an important step toward specifying what good explanations are by analyzing the epistemically accessible and pragmatic aspects of explanations. We characterize sufficiently good, or fair and adequate, explanations in terms of counterfactuals and what we call the conundra of the explainee, the agent that requested the explanation. We provide a correspondence between logical and mathematical formulations for counterfactuals to examine the partiality of counterfactual explanations that can hide biases;we define fair and adequate explanations in such a setting. We then provide formal results about the algorithmic complexity of fair and adequate explanations. Copyright © 2020, The Authors. All rights reserved.

关键词： parallel processing systems

Towards personalized computer simulations of breast cancer treatment

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Köhn-Luque, Alvaro Lai, Xiaoran Frigessi, Arnoldo Oslo Centre for Biostatistics and Epidemiology University of Oslo Norway

Sea Ship Target Detection Method of Remote Sensing Image

学校读者我要写书评

暂无评论

Sea Ship Target Detection Method of Remote Sensing Image

2019 International Conference on Artificial Intelligence and Advanced Manufacturing, AIAM 2019

作者： He, Baigen Kong, Xiangying Li, Liang Jiangsu Automation Research Institute of CSIC Lianyungang222006 China

ISBN: (纸本)9781728146911

Objective: Sea ship target detecting in both military and civilian application has very important practical value. Lots of domestic and foreign experts have carried out extensive research in this field, but contradictions in robustness and the presence of algorithmic complexity make it difficult to meet the needs of embedded board-level applications. So, this paper designed a real time ship target detection algorithm based on Canny operator and two-parameter CFAR algorithm to meet the DSP+FPGA embedded systems. Method: firstly, we use the Canny operator detect edge information to detect rough location of the ship, then use the two-parameter CFAR algorithm identify targets, and thus retaining the advantages of two-meter CFAR algorithm, while reducing computation time. Result: Experimental results indicate that the method in this paper can detect both bright and dark sea ship target of remote sensing image accurately and efficiently. Conclusion: It can satisfy the system requirements of real-time embedded board ship target detection. © 2019 IEEE.

关键词： parallel processing systems

An operational characterization of mutual information in algorithmic information theory

学校读者我要写书评

暂无评论

An operational characterization of mutual information in alg...

作者： Romashchenko, Andrei Zimand, Marius LIRMM Univ Montpellier CNRS 161 rue Ada Montpellier34095 France Department of Computer and Information Sciences Towson University 7800 York Road TowsonMD21252 United States

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties-one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair-can establish via a probabilistic protocol with interaction on a public channel. For l > 2, the longest shared secret that can be established from a tuple of strings (x1, ..., xl ) by l parties-each one having one component of the tuple and the complexity profile of the tuple-is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： parallel processing systems