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

LD: A Polynomial Time Algorithm for Tree Isomorphism

Procedia Engineering 2011年 15卷 2015-2020页

作者： Baida Zhang Yuhua Tang Junjie Wu Shuai Xu National laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Changsha Hunan 410073 P. R. China Department of Information Engineering Academy of Armored Force Engineering Beijing 100000 P.R.China

Graph isomorphism problem has always been mathematics and engineering technology community concern, the reason mainly from two aspects: First, in theory, is generally believed that the problem is NP-complete problem; Second, the graph isomorphism the problem with good prospects, in chemistry, operations research, computer science, electronics, network theory has applications in many fields, but the exponential complexity of the algorithm and the algorithm itself makes the limitations applicable to the object involved with complex graphics the application of structure is difficult to determine the start. In this paper, class tree is proposed based on the node to delete the exact graph isomorphism problem, you can quickly determine the graph isomorphism problem, and theoretical analysis and experiments show that the algorithm can determine the class in polynomial time tree isomorphism problem.

关键词： Graph Isomorphism LD algorithm

来源：评论

学校读者我要写书评

暂无评论

An Energy-Efficient Scheduling Algorithm for Sporadic Real-Time Tasks in Multiprocessor Systems

An Energy-Efficient Scheduling Algorithm for Sporadic Real-T...

引用

IEEE International Conference on High Performance Computing and Communications (HPCC)

作者： Dong-Song Zhang Fang-Yuan Chen Hong-Hua Li Shi-Yao Jin De-Ke Guo National Laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Changsha China School of Computing Science Simon Fraser University Burnaby BC Canada National Laboratory for Information System Engineering School of Information Systems and Management National University of Defense Technology Changsha China

As the energy consumption of embedded multiprocessor systems becomes increasingly prominent, the real-time energy-efficient scheduling in multiprocessor systems becomes an urgent problem to reduce the system energy consumption while meeting real-time constraints. For a multiprocessor with independent DVFS and DPM at each processor, this paper proposes an energy-efficient real-time scheduling algorithm named LRE-DVFS-EACH, based on LRE-TL which is an optimal real-time scheduling algorithm for sporadic tasks. LRE-DVFS-EACH utilizes the concept of TL plane and the idea of fluid scheduling to dynamically scale the voltage and frequency of processors at the initial time of each TL plane as well as the release time of a sporadic task in each TL plane. Consequently, LRE-DVFS-EACH can obtain a reasonable tradeoff between the real-time constraints and the energy saving. LRE-DVFS-EACH is also adaptive to the change of workload caused by the dynamic release of sporadic tasks, which can obtain more energy savings. The experimental results show that compared with existing algorithms, LRE-DVFS-EACH can not only guarantee the optimal feasibility of sporadic tasks, but also achieve more energy savings in all cases, especially in the case of high workloads.

关键词： Real time systems Scheduling algorithm Time frequency analysis Scheduling Heuristic algorithms Power demand

来源：评论

学校读者我要写书评

暂无评论

Accelerating MatLab code using GPU: A review of tools and strategies

Accelerating MatLab code using GPU: A review of tools and st...

引用

2011 2nd International Conference on Artificial Intelligence, Management science and Electronic Commerce, AIMSEC 2011

作者： Zhang, Baida Xu, Shuai Zhang, Feng Bi, Yuan Huang, Linqi National Laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Changsha 410073 China Department of Information Engineering Academy of Armored Force Engineering Beijing 100000 China Electronic Information Industry Co. Ltd Beijing 100085 China Naval Academy of Armament Beijing 100036 China School of Resources and Safety Engineering Central South University Changsha 410083 China

ISBN: (纸本)9781457705366

Lots of toolboxes of accelerating MatLab using GPU are available now[1], but, users are confused by which toolbox is best suitable for a particular task. Three toolboxes-Jacket, GPUmat, and parallel Computing Toolbox of MatLab are selected. For each toolbox, its advantages and pitfalls are reviewed, with an aim to allow the reader to identify which toolbox is appropriate for a given task. Strategies of whether a function should execute on GPU are given after a formula analysis. The analysis is also a framework for program automatically decides which function is cost-efficient to execute on GPU. A series of benchmark of different types of computing, including data transfer between GPU and CPU, data matrix Generation, matrix operation and GPU functions were tested in all three toolboxes. And the results show that Jacket is the best one. Some advices to improve the performance of toolboxes are given in the end. © 2011 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

A review on the churn character of P2P networks

引用

Jisuanji Xuebao/Chinese Journal of Computers 2011年第9期34卷 1563-1577页

作者： Fu, Zhi-Peng Wang, Huai-Min Shi, Dian-Xi Zou, Peng School of Computer Science National University of Defense Technology Changsha 410073 China National Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha 410073 China

P2P application is one of the most popular applications in the Internet, but its performance is badly influenced by the churn character-the nodes continuous arrival and departure. On the basis of introducing the origin of the churn, the definition of it and its influences to the P2P system performance, we minutely describe the research on the statistical properties, and discover some dynamic law including nodes' session time generally obey the heavy-tailed distribution. Then we detail the measurement methods. For passive monitoring, active monitoring, sample and so on, we present the advantages and disadvantages of each method, and explain the corresponding improving method to enhance the accuracy of the measurement. After that we elaborate the resilience strategies to the churn. Towards the neighbor selection, failure recovery, replica maintenance, link lifetime maintenance and so on, we present also the advantage and disadvantage of each strategy, and present our view to each of aspects. Finally, the summary and prospect of the future research are given.

关键词： Peer to peer networks

来源：评论

学校读者我要写书评

暂无评论

A multi-layered emulation platform to verify the effectiveness of consistency control approaches about message ordering

A multi-layered emulation platform to verify the effectivene...

引用

International Conference on Communication Software and Networks, ICCSN

作者： Hangjun Zhou Sha Fu Key Laboratory of Science and Technology for National Defence of Parallel and Distributed P rocessing School of Computer Science National University of Defense Technology Changsha Hunan China Department of Information Management Hunan University of Finance and Economics Changsha Hunan China

It is an important issue to preserve the consistent delivering order of messages at each site in distributed Virtual Environments(DVEs). Currently, the violations of message delivery order are inclined to happen in the large-scale and frequently interactive DVEs running on Wide Area Network(WAN). The inconsistent anomalies are characterized as unpredictable, unrepeatable and uncontrollable, which results in the severe problem for the development of the consistency control approaches. Meanwhile, it is also highly expensive to directly verify the proposed approaches on WAN. Therefore, in this paper, we design and establish an original multi-layered emulation platform in LAN, which can emulate the network latency of WAN and repeat the scenarios of violations. On the platform, the designers of consistency approaches don't have to spend efforts to realize the fundamental functions of the verification, but could pay more attention to the development and optimization of the control algorithms, which is very beneficial for the improvement of message ordering approaches.

关键词： Switches Wide area networks

来源：评论

学校读者我要写书评

暂无评论

A Unique Vertex Deleting Algorithm for Graph Isomorphism

A Unique Vertex Deleting Algorithm for Graph Isomorphism

引用

International Symposium on Image and Data Fusion (ISIDF)

作者： Baida Zhang Yuhua Tang Junjie Wu Linqi Huang National laboratory for Parallel and Distributed Processing School of Computer National University of Defense Technology Changsha Hunan P. R. China School of Resources and Safety Engineering Central South University Changsha P. R. China

Graph isomorphism problem has applications in many fields, such as chemistry, computer science, electronics, and network theory. But the exponential complexity of the algorithm makes the testing is time consuming. In this paper, a new algorithm named Unique Vertex Delete (UVD for short) is presented to speed up the process of isomorphic testing. The main idea of UVD algorithm is deleting vertex continuously to reduce the scale of the problem, and new field is added for each vertex to indicate the information of deleted neighbor vertices. Theoretical analysis and experiments show that the UVD algorithm consistently and significantly outperforms existing state-of-the-art approaches.

关键词： Algorithm design and analysis Testing Educational institutions Polynomials Software algorithms Complexity theory Partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

Superscalar communication: A runtime optimization for distributed applications

引用

science China(Information sciences) 2010年第10期53卷 1931-1946页

作者： LI HuiBa , LIU ShengYun, PENG YuXing, LI DongSheng, ZHOU HangJun & LU XiCheng National laboratory for parallel and distributed processing, National University of Defense technology, Changsha 410073, China 1. National Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha 410073 China

Building distributed applications is difficult mostly because of concurrency management. Existing approaches primarily include events and threads. Researchers and developers have been debating for decades to prove which is superior. Although the conclusion is far from obvious, this long debate clearly shows that neither of them is perfect. One of the problems is that they are both complex and error-prone. Both events and threads need the programmers to explicitly manage concurrencies, and we believe it is just the source of difficulties. In this paper, we propose a novel approach—superscalar communication, in which concurrencies are automatically managed by the runtime system. It dynamically analyzes the programs to discover potential concurrency opportunities; and it dynamically schedules the communication and the computation tasks, resulting in automatic concurrent execution. This approach is inspired by the idea of superscalar technology in modern microprocessors, which dynamically exploits instruction-level parallelism. However, hardware superscalar algorithms do not fit software in many aspects, thus we have to design a new scheme completely from scratch. Superscalar communication is a runtime extension with no modification to the language, compiler or byte code, so it is good at backward compatibility. Superscalar communication is likely to begin a brand new research area in systems software, which is characterized by dynamic optimization for networking programs.

关键词： network programming concurrency event thread superscalar

来源：评论

学校读者我要写书评

暂无评论

FPQRNA: Hardware-accelerated qrna package for noncoding rna gene detecting on FPGA

引用

Journal of Bioinformatics and Computational Biology 2010年第4期8卷 743-761页

作者： Xia, Fei Dou, Yong Lei, Guo-Qing National Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha 410073 China

Noncoding RNAs (ncRNAs) have important functional roles in biological processes and have become a central research interest in modern molecular biology. However, how to find ncRNA attracts much more attention since ncRNA gene sequences do not have strong statistical signals, unlike protein coding genes. QRNA is a powerful program and has been widely used as an efficient analysis tool to detect ncRNA gene at present. Unfortunately, the O(L ³) computing requirements and complicated data dependency greatly limit the usefulness of QRNA package with the explosion in gene database. In this paper, we present a fine-grained parallel QRNA prototype system, FPQRNA, for accelerating ncRNA gene detection application on FPGA chip. We propose a systolic-like array architecture with multiple PEs (processing Elements). We partition the tasks by columns and assign tasks to PEs for load balance. We exploit data reuse schemes to reduce the need to load matrices from external memory. The experimental results show a speedup factor of more than 18× over the QRNA - 2.0.3c software running on a PC platform with AMD Phenom 9650 Quad CPU for pairwise sequence alignment with 996 residues, however the power consumption of our FPGA accelerator is only about 30% of that of the general-purpose microprocessors. © 2010 Imperial College Press.

关键词： Bioinformatics fine-grained parallelism FPGA hardware accelerator noncoding RNA

来源：评论

学校读者我要写书评

暂无评论

A data communication scheduler for stream programs on CPU-GPU platform

A data communication scheduler for stream programs on CPU-GP...

引用

10th IEEE International Conference on Computer and Information technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010

作者： Tang, Tao Xu, Xinhai Lin, Yisong National Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha China

ISBN: (纸本)9780769541082

In recent years, heterogeneous parallel system have become a focus research area in high performance computing field. Generally,in a heterogeneous parallel system, CPU provides the basic computing environment and special purpose accelerator (GPU in this paper) provides high computing performance. However, the overall performance of the system is prone to be limited by the data communication between the CPU and the GPU. Data communication is typically used to synchronize the array on the CPU and the stream (in AMD's terminology) on the GPU. In many cases, programmers just add data synchronization for each GPU invoking independently. It is easy to program in this manner but much redundant communication may be introduced, which will dramatically degrade the overall performance. To alleviate this problem, based on the stream programming model, we propose a heuristic data communication schedule approach in this paper. By analyzing the state transition of stream/array data pair, relaxing the synchronization strategy conditionally and considering optimization for branch and loop control structure, our approach can significantly reduce the redundant data communication in most cases. © 2010 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Automatic concurrency management for distributed applications

Automatic concurrency management for distributed application...

引用

15th IEEE Symposium on Computers and Communications, ISCC 2010

作者： Li, Huiba Liu, Shengyun Peng, Yuxing Li, Dongsheng National Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha China

ISBN: (纸本)9781424477555

Building distributed applications is difficult mostly because of concurrency management. Existing approaches primarily include events and threads. Researchers and developers have been debating for decades to prove which is superior. Although the conclusion is far from obvious, this long debate clearly shows that neither of them is perfect. One of the problems is that they are both complex and error-prone. Both events and threads need the programmers to explicitly manage concurrency, and we believe it is just the source of difficulties. In this paper, we propose a novel approach-automatic concurrency management by the runtime system. It dynamically analyzes the programs to discover potential concurrency opportunities;and it dynamically schedules the communication and the computation tasks, resulting in automatic concurrent execution. This approach is inspired by the instruction scheduling technologies used in modern microprocessors, which dynamically exploits instruction-level parallelism. However, hardware scheduling algorithms do not fit software in many aspects, thus we have to design a new scheme completely from scratch. automatic concurrency management is a runtime technique with no modification to the language, compiler or byte code, so it is good at backward compatibility. It is essentially a dynamic optimization for networking programs. © 2010 IEEE.

关键词： Scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：