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

An efficient algorithm for managing a parallel heap

parallel Algorithms and Applications 1994年第3-4期4卷 281-299页

作者： Das, Sajal K. Horng, Wen-Bing Moon, Gyo S. Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX 76203-6886 United States Dept. of Computer Science and Information Engineering Tamkang Univ Tamsui Taipei Taiwan

We design a cost-optimal algorithm for managing a parallel heap on an exclusive-read exclusive-write (EREW), parallel random access machine (PRAM) model. We also analyze the time and space complexities of our algorithm, which efficiently employs p processors in the range 1 ≤ p ≤ n, where n is the maximum number of items in the parallel heap. It is assumed that a delete-think-insert cycle is repeatedly performed, and each processor requires an arbitrary but the same amount of time (called the think time) for processing an item which in turn generates at most two new items. The use of a global data structure for each level of the heap helps reduce the working memory space required. The time complexity for deleting p items of the highest priority from the parallel heap is O(log p), while that for inserting at most 2p new items is O(log n). With or without incorporating the think time, the speedup of our algorithm is shown to be linear, i.e. O(p). Hence this algorithm is an improvement in time over the one proposed by Deo and Prasad [5, 6]. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Data structure EREW PRAM Heap Linear speedup parallel algorithm Priority queue

来源：评论

学校读者我要写书评

暂无评论

Incremental capacitance extraction and its application to iterative timing-driven detailed routing 99

Incremental capacitance extraction and its application to it...

引用

Proceedings of the 1999 international symposium on Physical design

作者： Yanhong Yuan Prithviraj Banerjee Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL

来源：评论

学校读者我要写书评

暂无评论

Tree based data aggregation in sensor networks using polynomial regression

Tree based data aggregation in sensor networks using polynom...

引用

2005 8th International Conference on Information Fusion, FUSION

作者： Banerjee, Torsha Chowdhury, Kaushik Agrawal, Dharma P. University of Cincinnati OBR Center for Distributed and Mobile Computing Cincinnati OH 45221-0030 United States OBR Center for Distributed and Mobile Computing Department of Electrical and Computer Engineering and Computer Science University of Cincinnati Cincinnati OH 45221-0030 United States

ISBN: (纸本)0780392868

In this paper, we propose a tree based regression algorithm, (TREG) that addresses the problem of data compression in wireless sensor networks. By function approximation based on multivariable polynomial regression and passing only the coefficients returned by the regression function instead of aggregated data, TREG achieves the following goals: (1) the sink can get attribute values in regions devoid of sensor nodes for attribute values that show smooth spatial gradation (2) readings over any portion of the region can be obtained at one time by querying the root instead of flooding those regions, thus incurring significant energy savings. As size of the data packet transmitted from one tree node to another remains constant, the proposed scheme scales well with growing network density. Extensive simulations are performed on real world data to demonstrate the effectiveness of our aggregation algorithm. Results reveal that for a network density of 0.0025, the optimal tree-depth should be 4 in order to restrict the absolute error to less than a threshold of 6%. A data compression ratio of about 0.02 is achieved using our proposed algorithm, which is almost independent of tree depth. © 2005 IEEE.

关键词： Data reduction

来源：评论

学校读者我要写书评

暂无评论

A Java graphical user interface for large-scale scientific computations in distributed systems

A Java graphical user interface for large-scale scientific c...

引用

International Conference on High Performance computing in the Asia-Pacific Region

作者： X. Shen G. Thiruvathukal W. Liao A. Choudhary A. Singh Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL USA

Large-scale scientific applications present great challenges to computational scientists in terms of obtaining high performance and in managing large datasets. These applications (most of which are simulations) may employ multiple techniques and resources in a heterogeneously distributed environment. Effective working in such an environment is crucial for modern large-scale simulations. In this paper, we present an integrated Java graphical user interface (IJ-GUI) that provides a control platform for managing complex programs and their large datasets easily. As far as performance is concerned, we present and evaluate our initial implementation of two optimization schemes: data replication and data prediction. Data replication can take advantage of 'temporal locality' by caching the remote datasets on local disks; data prediction, on the other hand, provides prefetch hints based on the datasets' past activities that are kept in databases. We first introduce the data contiguity concept in such an environment that guides data prediction. The relationship between the two approaches is discussed.

关键词： Java Graphical user interfaces Large-scale systems computer interfaces distributed computing Computational modeling Visual databases Analytical models Data analysis Data visualization

来源：评论

学校读者我要写书评

暂无评论

A distributed Multi-Storage Resource Architecture and I/O Performance Prediction for Scientific computing

引用

Cluster computing 2003年第3期6卷 189-200页

作者： Shen, X. Choudhary, A. Matarazzo, C. Sinha, P. Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston USA Lawrence Livermore National Laboratory Livermore USA

I/O intensive applications have posed great challenges to computational scientists. A major problem of these applications is that users have to sacrifice performance requirements in order to satisfy storage capacity requirements in a conventional computing environment. Further performance improvement is impeded by the physical nature of these storage media even when state-of-the-art I/O optimizations are employed. In this paper, we present a distributed multi-storage resource architecture, which can satisfy both performance and capacity requirements by employing multiple storage resources. Compared to a traditional single storage resource architecture, our architecture provides a more flexible and reliable computing environment. This architecture can bring new opportunities for high performance computing as well as inherit state-of-the-art I/O optimization approaches that have already been developed. It provides application users with high-performance storage access even when they do not have the availability of a single large local storage archive at their disposal. We also develop an Application Programming Interface (API) that provides transparent management and access to various storage resources in our computing environment. Since I/O usually dominates the performance in I/O intensive applications, we establish an I/O performance prediction mechanism which consists of a performance database and a prediction algorithm to help users better evaluate and schedule their applications. A tool is also developed to help users automatically generate performance data stored in databases. The experiments show that our multi-storage resource architecture is a promising platform for high performance distributed computing.

关键词：

来源：评论

学校读者我要写书评

暂无评论

DPFS: a distributed parallel file system

DPFS: a distributed parallel file system

引用

International Conference on parallel Processing (ICPP)

作者： Xiaohui Shen A. Choudhary Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL USA

One of the challenges brought by large-scale scientific applications is how to avoid remote storage access by collectively using enough local storage resources to hold huge amount of data generated by the simulation while providing high performance I/O. DPFS, a distributed parallel File System, is designed and implemented to address this problem. DPFS collects locally distributed unused storage resources as a supplement to the internal storage of parallel computing systems to satisfy the storage capacity requirement of large-scale applications. In addition, like parallel file systems, DPFS provides striping mechanisms that divides a file into small pieces and distributes them across multiple storage devices for parallel data access. The unique feature of DPFS is that it provides three file levels with each file level corresponding to a file striping method. In addition to the traditional linear striping method, DPFS also provides a novel multidimensional striping method that can solve performance problems of linear striping for many popular access patterns. Other issues such as load-balancing and user interface are also addressed in DPFS.

关键词： File systems parallel processing Large-scale systems Spatial databases distributed computing distributed power generation Computational modeling computer simulation Multidimensional systems Ear

来源：评论

学校读者我要写书评

暂无评论

An integrated graphical user interface for high performance distributed computing

An integrated graphical user interface for high performance ...

引用

International Symposium on Database engineering and Applications (IDEAS)

作者： X. Shen W.-K. Liao A. Choudhary Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL USA

ISBN: (纸本)0769511406

It is very common that modern large-scale scientific applications employ multiple compute and storage resources in a heterogeneously distributed environment. Working effectively and efficiently in such an environment is one of the major concerns for designing meta-data management systems. The authors present an integrated graphical user interface (GUI) that makes the entire environment virtually an easy-to-use control platform for managing complex programs and their large datasets. To hide the I/O latency when the the user carries out interactive visualization, aggressive prefetching and caching techniques are employed in our GUI. The performance numbers show that the design of our Java GUI has achieved the goals of both high performance and ease-of-use.

关键词： Graphical user interfaces distributed computing Analytical models Delay Data visualization Prefetching Visual databases Large-scale systems Environmental management Java

来源：评论

学校读者我要写书评

暂无评论

On reducing false sharing while improving locality on shared memory multiprocessors

On reducing false sharing while improving locality on shared...

引用

International Conference on parallel Architecture and Compilation Techniques (PACT)

作者： M. Kandemir A. Choudhary J. Ramaujam P. Banerjee Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL USA

The performance of applications on large shared-memory multiprocessors with coherent caches depends on the interaction between the granularity of data sharing, the size of the coherence unit and the spatial locality exhibited by the applications, in addition to the amount of parallelism in the applications. Large coherence units are helpful in exploiting spatial locality, but worsen the effects of false sharing. We present a mathematical framework that allows a clean description of the relationship between spatial locality and false sharing. We first show how to identify a severe form of multiple-writer false sharing and then demonstrate the importance of the interaction between optimization techniques aimed at enhancing locality and the techniques oriented toward reducing false sharing. Given the conflicting requirements, a compiler based approach to this problem holds promise. We investigate the use of data transformations in addressing spatial locality and false sharing, and derive an approach that balances the impact of the two. Experimental results demonstrate that such a balanced approach outperforms those approaches that consider only one of these two issues. On an eight-processor SGI Origin 2000 system, our approach brings an additional 9% improvement over a powerful locality optimization technique that uses both loop and data transformations. Also, our approach obtains an additional 19% improvement over an optimization technique that is oriented specifically toward reducing false sharing.

关键词： parallel machines Random access memory Cost function parallel processing Concurrent computing

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for power estimation

Parallel algorithms for power estimation

引用

Design Automation Conference

作者： V. Kim P. Banerjee Center for Parallel and Distributed Computing Department of Electrical and Computer Engineering Northwestern University Evanston IL USA

Several techniques currently exist for estimating the power dissipation of combinational and sequential circuits using exhaustive simulation, Monte Carlo sampling, and probabilistic estimation. Exhaustive simulation and Monte Carlo sampling techniques can be highly reliable but often require long runtimes. This paper presents a comprehensive study of pattern-partitioning and circuit-partitioning parallelization schemes for those two methodologies in the context of distributed-memory multiprocessing systems. Issues in pipelined event-driven simulation and dynamic load balancing are addressed. Experimental results are presented for an IBM SP-2 system and a network of HP-9000 workstations. For instance, runtimes have been reduced from over 3 hours to under 20 minutes in one case.

关键词： parallel algorithms Circuit simulation Monte Carlo methods Runtime Power dissipation Sequential circuits Power system reliability Multiprocessing systems Discrete event simulation Load management

来源：评论

学校读者我要写书评

暂无评论

MS-I/O: A distributed Multi-Storage I/O System 02

MS-I/O: A Distributed Multi-Storage I/O System

引用

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

作者： Xiaohui Shen A. Choudhary Department of Electrical and Computer Engineering Center for Parallel and Distributed Computing Northwestern University Evanston IL USA

ISBN: (纸本)9780769515823

More and more parallel applications are running in a distributed environment to take advantage of easily available and inexpensive commodity resources. For data intensive applications, employing multiple distributed storage resources has many advantages. In this paper, we present a Multi-Storage I/O System (MS-I/O) that can not only effectively manage various distributed storage resources in the system, but also provide novel high performance storage access schemes. MS-I/O employs many state-of-the-art I/O optimizations such as collective I/O, asynchronous I/O etc. and a number of new techniques such as data location, data replication, subfile, superfile and data access history. In addition, many MS-I/O optimization schemes can work simultaneously within a single data access session, greatly improving the performance. Although I/O optimization techniques can help improve performance, it also complicates I/O system. In addition, most optimization techniques have their limitations. Therefore, selecting accurate optimization policies requires ex-pert knowledge which is not suitable for end users who may have little knowledge of I/O techniques. So the task of I/O optimization decision should be left to the I/O system itself, that is, automatic from user's point of view. We present a User Access Pattern data structure which is associated With each dataset that can help MS-I/O easily make accurate I/O optimization decisions.

关键词： distributed computing Application software Resource management Prefetching History Data structures Communications technology parallel processing computer networks Concurrent computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：