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

Towards estimating expected sizes of probabilistic skylines

Science China(Information Sciences) 2011年第12期54卷 2574-2584页

作者： YANG YongTao & WANG YiJie national key laboratory for parallel and distributed processing, School of Computer, national University of Defense Technology, Changsha 410073, China 1. National Key Laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Changsha 410073 China

We consider the maximal vector problem on uncertain data, which has been recently posed by the study on processing skyline queries over a probabilistic data stream in the database context. Let D n be a set of n points in a d-dimensional space and q (0 < q 1) be a probability threshold; each point in D n has a probability to occur. Our problem is concerned with how to estimate the expected size of the probabilistic skyline, which consists of all the points that are not dominated by any other point in D n with a probability not less than q. We prove that the upper bound of the expected size is O(min{n, (- ln q)(ln n) d-1 }) under the assumptions that the value distribution on each dimension is independent and the values of the points along each dimension are distinct. The main idea of our proof is to find a recurrence about the expected size and solve it. Our results reveal the relationship between the probability threshold q and the expected size of the probabilistic skyline, and show that the upper bound is poly-logarithmic when q is not extremely small.

关键词： probabilistic skyline probabilistic data streams expected size

来源：评论

学校读者我要写书评

暂无评论

Speeding up the MATLAB complex networks package using graphic processors

引用

Chinese Physics B 2011年第9期20卷 460-467页

作者：张百达唐玉华吴俊杰李鑫 National laboratory for Parallel and Distributed Processing School of ComputerNational University of Defense Technology Department of Computer Science and Technology School of ComputerNational University of Defense Technology

The availability of computers and communication networks allows us to gather and analyse data on a far larger scale than previously. At present, it is believed that statistics is a suitable method to analyse networks with millions, or more, of vertices. The MATLAB language, with its mass of statistical functions, is a good choice to rapidly realize an algorithm prototype of complex networks. The performance of the MATLAB codes can be further improved by using graphic processor units （GPU）. This paper presents the strategies and performance of the GPU implementation of a complex networks package, and the Jacket toolbox of MATLAB is used. Compared with some commercially available CPU implementations, GPU can achieve a speedup of, on average, 11.3x. The experimental result proves that the GPU platform combined with the MATLAB language is a good combination for complex network research.

关键词： complex networks graphic processors unit MATLAB Jacket Toolbox

来源：评论

学校读者我要写书评

暂无评论

Betweenness-based algorithm for a partition scale-free graph

引用

Chinese Physics B 2011年第11期20卷 556-564页

作者：张百达吴俊杰唐玉华周静 National Laboratory for Parallel and Distributed Processing School of ComputersNational University of Defense Technology Department of Computer Science and Technology School of ComputersNational University of Defense Technology

Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.

关键词： graph partitioning betweenness-based partitioning algorithm scale free network

来源：评论

学校读者我要写书评

暂无评论

Heterogeneity-aware Peak Power Management for Accelerator-based Systems

Heterogeneity-aware Peak Power Management for Accelerator-ba...

引用

17th IEEE International Conference on parallel and distributed Systems (ICPADS)

作者： Wang, Guibin Lin, Yisong National Laboratory for Parallel and Distributed Processing National University of Defense Technology China

ISBN: (纸本)9780769545769

Power management has become one of the first-order considerations in high performance computing field. Many recent studies focus on optimizing the performance of a computer system within a given power budget. However, most existing solutions adopt fixed period control mechanism and are transparent to the running applications. Although the application-transparent control mechanism has relatively good portability, it exhibits low efficiency in accelerator-based heterogeneous parallel systems. In typical accelerator-based parallel systems, different processing units have largely different processing speeds and power consumption. Under a given power constraint, how to choose the processor to be slowed down and how to schedule a parallel task onto different processors for the maximum performance are different from those in homogeneous systems and have not been well studied. From the motivating example in this paper, we could find that in order to efficiently harness the heterogeneous parallel processing, one should not only perform dynamic voltage/frequency scaling (DVFS) to meet the power budget, but also tune the parallel task scheduling to adapt to the changes. In this paper, we propose a heterogeneity-aware peak power management, which extends existing application-transparent power controller with an application-aware power controller. Firstly, we theoretically analyze the conditions for the maximum performance given a power budget for heterogeneous systems. Based on this result, we provide a power-constrained parallel task partition algorithm, which coordinates parallel task partition and voltage scaling for heterogeneous processing units to achieve the optimal performance given a system power budget. Finally, we evaluate the proposed method on a typical CPU-GPU heterogeneous system, and validate the superiority of application-aware power controller over the existing method.

关键词： Accelerator-based Systems Peak Power Management GPU

来源：评论

学校读者我要写书评

暂无评论

PS-SIM: An Execution-Driven Performance Simulation Technology Based on Process-Switch

PS-SIM: An Execution-Driven Performance Simulation Technolog...

引用

International Conference on Advances in Computer Science, Environment, Ecoinformatics, and Education

作者： Guo, Xiaowei Lin, Yufei Xu, Xinhai Zhang, Xin National Laboratory for Parallel and Distributed Processing National University of Defense Technology China

ISBN: (纸本)9783642233234

Nowadays, the performance of large-scale parallel computer system improves continuously, and the system scale becomes extremely large. Performance prediction has become an important approach to guide system design, implementation and optimization. Simulation method is the most widely used performance prediction technology for large-scale parallel computer system. In this paper, after analyzing the extant problems, we proposed a novel execution-driven performance simulation technology based on process-switch. We designed a simulation framework named PS-SIM, and implemented a prototype system based on MPICH2. Finally, we verified the proposed approach by experiments. Experimental results show that the approach has high accuracy and simulation performance.

关键词： Performance Prediction Large-Scale parallel Computer System Execution-Driven Simulation MPICH

来源：评论

学校读者我要写书评

暂无评论

A performance study of CSMA in wireless networks with successive interference cancellation

A performance study of CSMA in wireless networks with succes...

引用

IEEE International Conference on Communications (ICC)

作者： Shaohe Lv Weihua Zhuang Xiaodong Wang Chi Liu Xiaofeng Hu Yipin Sun Xingming Zhou Institute of Network Information and Security National University of Defense Technology Changsha China Department of Electrical and Computer Engineering University of Waterloo Waterloo ONT Canada Central South University Changsha China National Laboratory of Parallel and Distributed Processing National University of Defense Technology Changsha China

Successive interference cancellation (SIC) is an effective way of multipacket reception to combat interference. As conventional CSMA (Carrier Sense Multiple Access) is designed for single packet reception, it is unclear whether or not CSMA performs well to exploit the SIC capability. In this paper, we analyze the performance of a simple CSMA protocol in a network with SIC. For a given link, we derive the residing areas of an interfering node when simultaneous transmission is allowed and when the interference is harmful, respectively. We show that, though SIC provides many new transmission opportunities, CSMA cannot effectively exploit them. There is a fundamental tradeoff in a CSMA protocol between exploiting the transmission opportunities from SIC and capturing the harmful interference. In many cases, when CSMA achieves its best performance, almost all new transmission opportunities are not exploited. It is therefore very necessary to design a new distributed access protocol in wireless networks with SIC.

关键词： Silicon carbide Multiaccess communication Interference Receivers Propagation losses Protocols Wireless networks

来源：评论

学校读者我要写书评

暂无评论

A Compact Model for Multi-Island Single Electron Transistors

A Compact Model for Multi-Island Single Electron Transistors

引用

3rd IEEE International NanoElectronics Conference (INEC)/Symposium on Nanoscience and Nanotechnology in China

作者： Chi, Yaqing Zhong, Haiqin Zhang, Chao Fang, Liang National Key Laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Hunan 410073 China

ISBN: (纸本)9781424435449

Multi-island single electron transistor is an important kind of the single electron transistor, which is convenient to realize the controllable room temperature operation. A novel semi-empirical compact model for the Multi-island single electron transistor is proposed. The new approach combines the orthodox theory of the single electron tunneling through single coulomb island and a novel empirical analysis procedure for the chain of multi coulomb islands to solve the current of the whole multi-island single electron transistor. The tunneling rates are calculated based on the orthodox theory for the single electron tunneling. The tunneling currents representing the first splitted peaks in the coulomb oscillation curves are calculated according to the assumption that the currents through all the coulomb islands are equal to each other at the stable states, while the currents representing the other splitted peaks are constructed and merged together according to the empirical analysis. The model is verified by the traditional SET simulator SIMON and shows much faster calculation speed than SIMON. Therefore, the novel compact model is suitable for the large scale MISET circuit simulation.

关键词： Single Electron Transistor Coulomb Island Coulomb Oscillation Splitted Peak

来源：评论

学校读者我要写书评

暂无评论

Memory access characterization of scientific applications on GPU and its implication on low power optimization

Memory access characterization of scientific applications on...

引用

2011 International Conference on Computational and Information Sciences, ICCIS 2011

作者： Wang, Guibin National Laboratory for Parallel and Distributed Processing National University of Defense Technology China

ISBN: (纸本)9780769545011

Following current IC design technology trend, modern GPUs integrate more and more processing cores, and the speed gap between processor and memory system becomes even larger. As the number of cores continually increases, the available bandwidth per core decreases correspondingly. Therefore, memory access performance has been one of the most critical bottlenecks for better performance. This paper analyzes the impact of memory system on performance and scalability for GPU with several scientific applications using a cycle-accurate simulator. Two observations we make are (1) that memory bandwidth has relatively greater impact on performance than memory latency, because the latter factor could be well hidden with tremendous concurrent executing threads supported in modern GPU architecture, and (2) that through examining the performance scalability of variable active cores, using the maximum hardware-supported cores may not bring in better performance, especially for the memory-intensive applications. In the end we suggest a better power-efficient exploitation of GPU is to make judicious concurrency-throttling based on the memory usage in application. © 2011 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Communication-aware task partition and voltage scaling for energy minimization on heterogeneous parallel systems

Communication-aware task partition and voltage scaling for e...

引用

2011 12th International Conference on parallel and distributed Computing, Applications and Technologies, PDCAT 2011

作者： Wang, Guibin Song, Wei National Laboratory for Parallel and Distributed Processing National University of Defense Technology China

ISBN: (纸本)9780769545646

Heterogeneous parallel systems have become popular in general purpose computing and even high performance computing fields. There are many studies focused on harnessing heterogeneous parallel processing for better performance. However the energy optimization for heterogeneous system has not been well studied. Owing to the differences in performance and energy consumption, the energy optimization technique for heterogeneous system is different from the existing methods designed for homogeneous system. Besides typical voltage scaling method, reasonable task partitioning is also an essential method for optimizing energy consumption on heterogeneous systems. Through partitioning a data parallel task and mapping sub-tasks onto several processors, one could achieve better performance and reduced energy consumption. As the computation cost reduces with specific accelerators, the communication overhead becomes more prominent. Therefore, the task partition optimization should holistically consider the computation improvement and communication overhead to achieve higher energy efficiency. Typically, task partition and voltage scaling are not orthogonal and influence the effect of each other in the energy optimization problem. In order to harness both two knobs efficiently, this paper proposes an integer linear programming (ILP) based energy-optimal solution designed for heterogeneous system. We present a case study of optimizing MGRID benchmark on a typical CPU-GPU heterogeneous system. The experimental results demonstrate that the proposed method could exploit the heterogeneity in different processors and achieve improved energy efficiency. © 2011 IEEE.

关键词： Energy efficiency

来源：评论

学校读者我要写书评

暂无评论

Data parallelism exploiting for H.264 encoder

Data parallelism exploiting for H.264 encoder

引用

International Conference on Multimedia and Signal processing

作者： Wen, Mei Ren, Ju Wu, Nan Su, Huayou Xun, Changqing Zhang, Chunyuan Parallel and Distributed Processing Laboratory National University of Defense Technology Changsha China

ISBN: (纸本)9780769543567

Real-time H.264 encoding of high-definition (HD) video (up to 1080p) is a challenge workload to most existing programmable processors. Instead, the novel programmable parallel processors such as stream processor, Graphic processor unit (GPU) and DSP offer a different and very promising technology for these demands. Thus, parallel computing for H.264 encoding on these processors is becoming a hot research point. It's challenged, because most emerging parallel processors focus on supporting Data Level parallel (DLP), while the dependency inherently existing in traditional H.264 encoding algorithm significantly restricts exploiting DLP. Facing the challenge, this paper presents data parallel processing methods for key modules of H.264 encoder which can eliminate the dependency restriction. The result shows that key modules including Intra-prediction, Inter-prediction and CAVLC achieve significant speedup on stream processor by using these data parallel processing methods.© 2011 IEEE.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：