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

ONLINE sorting OF TWISTED SEQUENCES IN LINEAR TIME

BIT NUMERICAL MATHEMATICS 1988年第2期28卷 194-204页

作者： AURENHAMMER, F AUSTRIAN COMP SOC A-8010 GRAZ AUSTRIA GRAZ TECH UNIV INST INFORMAT PROC A-8010 GRAZ AUSTRIA

A sequence of real numbers is called twisted if it can be produced from the sorted sequence by repeatedly reversing the order of consecutive subsequences. It is shown that twisted sequences constitute a class of expon... 详细信息

关键词： E.2.2 F.2.1 sorting algorithm worst-case complexity ordered tree geometric interpretation convex hull

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient sorting with the distributed memory architecture ePUMA 14

Energy-efficient sorting with the distributed memory archite...

引用

13th IEEE International Symposium on Parallel and Distributed Processing with Applications

作者： Karlsson, Andreas Sohl, Joar Liu, Dake Linkoping Univ Dept Elect Engn S-58183 Linkoping Sweden

ISBN: (纸本)9781467379526

This paper presents the novel heterogeneous DSP architecture ePUMA and demonstrates its features through an implementation of sorting of larger data sets. We derive a sorting algorithm with fixed-size merging tasks suitable for distributed memory architectures, which allows very simple scheduling and predictable data-independent sorting time. The implementation on ePUMA utilizes the architecture's specialized compute cores and control cores, and local memory parallelism, to separate and overlap sorting with data access and control for close to stall-free sorting. Penalty-free unaligned and out-of-order local memory access is used in combination with proposed application-specific sorting instructions to derive highly efficient local sorting and merging kernels used by the system-level algorithm. Our evaluation shows that the proposed implementation can rival the sorting performance of high-performance commercial CPUs and GPUs, with two orders of magnitude higher energy efficiency, which would allow high-performance sorting on low-power devices.

关键词： DSP ePUMA sorting sorting programs grade Digital signal processing Desmoplakin Gene distributed memory architecture Local Memory energy component Energy efficiency sorting algorithm ARCHITECTURE Access to Information information retrieval

来源：评论

学校读者我要写书评

暂无评论

Induced sorting Suffixes in External Memory with Better Design and Less Space 1

引用

22nd International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Liu, Wei Jun Nong, Ge Chan, Wai Hong Wu, Yi Sun Yat Sen Univ Guangzhou 510275 Guangdong Peoples R China Gannan Normal Univ Ganzhou Peoples R China SYSU CMU Shunde Int Joint Res Inst Guangzhou Guangdong Peoples R China Hong Kong Inst Educ Tai Po Hong Kong Peoples R China

ISBN: (数字)9783319238265

ISBN: (纸本)9783319238265;9783319238258

Recently, several attempts have been made to extend the internal memory suffix array (SA) construction algorithm SA-IS to the external memory model, e.g., eSAIS, EM-SA-DS and DSA-IS. While the developed programs for these algorithms achieve remarkable performance in terms of I/O complexity and speed, their designs are quite complex and their disk requirements remain rather heavy. Currently, the core algorithmic part of each of these programs consists of thousands of lines in C++, and the average peak disk requirement is over 20n bytes for an input string of size n < 2(40). We re-investigate the problem of induced sorting suffixes in external memory and propose a new algorithm SAIS-PQ (SAIS with Priority Queue) and its enhanced alternative SAIS-PQ+. Using the library STXXL, the core algorithmic parts of SAIS-PQ and SAIS-PQ+ are coded in around 800 and 1600 lines in C++, respectively. The time and space performance of these two programs are evaluated in comparison with eSAIS that is also implemented using STXXL. In our experiment, eSAIS runs the fastest for the input strings not larger than 16 GiB, but it is slower than SAIS-PQ+ for the only two input strings of 32 and 48.44 GiB. For the average peak disk requirements, eSAIS and SAIS-PQ+ are around 23n and 15n bytes, respectively.

关键词： Suffix array sorting algorithm External memory

来源：评论

学校读者我要写书评

暂无评论

Implementation of Address-Based Data sorting on Different FPGA Platforms

Implementation of Address-Based Data Sorting on Different FP...

引用

IEEE East-West Design and Test Symposium (EWDTS)

作者： Mihhailov, Dmitri Sudnitson, Alexander Sklyarov, Valery Skliarova, Iouliia Tallinn Univ Technol Dept Comp Engn Tallinn Estonia Univ Aveiro DETI IEETA Aveiro Portugal

ISBN: (纸本)9781479920952;9781479920969

Among numerous tasks that need to be solved, sorting is considered to be one of the most important. Since it is time consuming for large volumes of data, acceleration is greatly required for many practical applications. It is also important to discover such methods that take advantage of the implementation platform (due to its uniqueness) and consider not only the number of the required operations, but also efficiency of their implementation in hardware circuits. This paper evaluates implementations of address-based data sorting algorithms in field-programmable gate array (FPGA) circuits. It is demonstrated that the proposed technique can be used efficiently both in low cost FPGAs as well as in advanced FPGAs, and the number of sorted items (with sizes of up to 32 bits) can reach 2(32).

关键词： Field programmable gate arrays grade Platform sorting programs Electric circuits sorting algorithm uniqueness

来源：评论

学校读者我要写书评

暂无评论

FPGA-based collaborative hardware sorting unit for embedded data processing system 10

FPGA-based collaborative hardware sorting unit for embedded ...

引用

10th International Conference on Intelligent Computation Technology and Automation (ICICTA)

作者： Long, Zou Zhang, Zhenrong Guangxi Univ Sch Comp Elect & Informat Nanning 530004 Peoples R China Guangxi Univ Guangxi Key Lab Multimedia Commun & Network Techn Cultivating Base Nanning 530004 Peoples R China Guangxi Univ Guangxi Coll & Univ Key Lab Multimedia Commun & I Nanning 530004 Peoples R China

ISBN: (纸本)9781538612309

In recent years there has been a growing interest in Internet of Thing, Big Data and Mobile Internet. With the rapid growth of the amount of data in the embedded environment, using a traditional embedded processor is hard to satisfy the requirements of big data processing. sorting is one of the fundamental operation in data processing and is also frequently used for search, filter, feature analysis and so on. It can contribute significantly to the overall execution time in a system. Existing techniques accelerate sorting using multiprocessor or GPUs, but it is impractical for embedded systems. In this paper, we propose a FPGA-based collaborative hardware sorting unit for embedded data processing. The waiting data is transferred from the embedded processor to our hardware sorting unit by the data bus, then a ordered sequence is given form hardware sorting unit and is returned to the embedded processor by data bus. The waiting data is processed in a pure hardware circuit, do not need anything software operation, so the calculating speed depends on the delay time of hardware circuit, which is faster than traditional iterative algorithm by software method. By the collaborative hardware unit, we can greatly reduce the processor load and improve the operation efficiency significantly. In addition, we can define the size of the data bit flexibly, we can also expend the scale of the unit by circuit topology.

关键词： FPGA data process sorting algorithm embedded system

来源：评论

学校读者我要写书评

暂无评论

Capacitor Balancing Controller Voltage sorting Statistics in Modular Multilevel Converters

Capacitor Balancing Controller Voltage Sorting Statistics in...

引用

IEEE Southern Power Electronics Conference (SPEC)

作者： Heath, Theodor Green, Peter R. Barnes, Mike Coventry, Paul Univ Manchester Sch Elect & Elect Engn Manchester Lancs England Natl Grid Warwick England

ISBN: (纸本)9781509064267;9781509064250

Modular multilevel converters (MMCs) are made up of many submodules (SMs) connected in series. In order to avoid semiconductor over-voltages, SM capacitors should be kept within strict voltage limits. The capacitor balancing controller (CBC) is used to sort SM capacitor voltages prior to modulation. This paper investigates the variation in sorting complexity at steady state and transient conditions for a brute-force and past-position methodology based on the bubble sort algorithm. A focus is placed on the potential for 'worst-case' sorting, requiring increased computational effort. This paper forms part of ongoing research to analyze the hardware constraints on MMCs with very large numbers of SMs. Simulation results based on a PSCAD/EMTDC detailed equivalent model are used for analysis and conclusions.

关键词： Modular Multilevel Converter Nearest Level Control Capacitor Balancing Control sorting algorithm

来源：评论

学校读者我要写书评

暂无评论

Customary Behavior of sorting Reals with Linear Time Complexity 2

Customary Behavior of Sorting Reals with Linear Time Complex...

引用

2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE)

作者： Jirina, Marcel Inst Comp Sci AS CR Dept Machine Learning Prague Czech Republic

ISBN: (纸本)9781728166957

sorting with real number keys has time complexity n log n. This holds under the assumption that for all n samples a comparison sort is used. Here we propose to use the counting sort with just n cells for initial placement of samples. We resolve cases of groups of several samples placed into one cell by a comparison sort. Surprisingly, even this part has time complexity proportional to n. Numerical experiments confirm this finding and shows influence of the computing environment such as paging, and reflects a higher speed than the quicksort.

关键词： sorting algorithm sorting reals linear time complexity countingsort

来源：评论

学校读者我要写书评

暂无评论

High-performance genome sorting program 10

High-performance genome sorting program

引用

10th International Young Scientists Conference in Computational Science (YSC)

作者： Kasilov, Vasily Drobintsev, Pavel Voinov, Nikita Peter Great St Petersburg Polytech Univ Polytech Skaya 29 St Petersburg 195251 Russia

This paper is devoted to the practical application of parallel sorting algorithms and parallel input-output methods for the problem of genome alignment. The paper considers different approaches to the implementation of such algorithms, taking into account the capabilities of high-performance systems. Main purpose of the work is to develop a genome sorting program, the efficiency of which significantly exceeds the efficiency of free software analogues. The genome sorting program is implemented for a supercomputer using the C++ language and the OpenMP and OpenMPI. The developed program demonstrates a significant increase in the speed of operation (up to 10 times) compared to free software analogues due to massive parallel data input and output. Different approaches for data input/output parallelization and data processing considered in the paper can be applied in other subject areas. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： genome sorting algorithm alignment BAM and SAM files OpenMP HPC

来源：评论

学校读者我要写书评

暂无评论

A New Hardware Accelerator for Data sorting in Area & Energy Constrained Architectures 62

A New Hardware Accelerator for Data Sorting in Area & Energy...

引用

62nd IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)

作者： Norollah, Amin Beitollahi, Hakem Patooghy, Ahmad Iran Univ Sci & Technol Sch Comp Engn Tehran Iran Univ Cent Arkansas Dept Comp Sci Conway AR USA

ISBN: (纸本)9781728127880

sorting is one of the most important computational tasks in data processing applications. Recent studies show that the FPGA-based hardware accelerators are more efficient than the general-purpose processors and GPUs. By increasing the input records in the sorting network, the number of Compare-And-Swap (CAS) units would be increased, which in turn, will lead to increased resource consumption. In some applications, the number of available resources is limited. Thereby, it is necessary to optimize resource requirements while maintaining a sufficient level of performance. This paper presents a new sorting architecture that reduces the number of required resources compared to the state-of-the-art sorting architecture and achieves the desired performance using Unary processing. Results indicate that the proposed architecture increases throughput by 29.1% and reduces the number of LUTs by 42%, for sorting 8-input records, compared to other architecture.

关键词： FPGA hardware accelerator unary processing stochastic processing sorting algorithm Bitonic sorting network

来源：评论

学校读者我要写书评

暂无评论

Lossless compression of medical image by hierarchical sorting

Lossless compression of medical image by hierarchical sortin...

引用

23rd Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society

作者： Myojoyama, A Yamamoto, T Hokkaido Univ Grad Sch Engn Sapporo Hokkaido Japan

ISBN: (纸本)0780372115

We propose a new lossless compression method for medical images, based on a hierarchical sorting. Hierarchical sorting is a technique that achieves a high compression ratio by detecting the regions where image patterns change abruptly, and by sorting pixel order by value to increase predictability. This method enables control of sorting accuracy along with size and complexity. As a result, we can reduce the sizes of the permutation tables and reuse the tables for other image regions. Comparison of this method through experiment reveals better performance for medical images generated by X-ray CT, MRI and large size CR . DR instruments. This technique applies a quad-tree division method to divide an image into blocks in order to support progressive decoding and fast preview of large images.

关键词： lossless compression medical image sorting algorithm hierarchical coding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：