sorting is one of the most fundamental operations in computer programming and used in countless algorithms. The performance of traditional von Neumann computers running sorting is limited by the bandwidth between memo...
详细信息
ISBN:
(纸本)9798350380415;9798350380408
sorting is one of the most fundamental operations in computer programming and used in countless algorithms. The performance of traditional von Neumann computers running sorting is limited by the bandwidth between memories and processors. Computing-in-memory (CiM) is a promising technology which has the potential to solve the "memory wall" bottleneck. CiM is suitable for data-intensive applications, and it is ideal for accelerating large-scale data sorting. In this paper, we propose a novel in-memory sorting accelerator, named MemSort, based on a proposed in-memory comparison array design based on emerging non-volatile devices. MemSort supports three sort operations including counting sort, merging sort, and the combination of counting sort and merging sort. We build a performance model for the combination sort which enables flexible allocation of resources under given constraints to meet the requirements of various applications for sorting. The evaluation results show that MemSort shows significant performance improvement and energy efficiency at both the system level and application level when processing large-scale data sorting. Compared with the CPU implementation, MemSort achieves energy savings of 19.69-72.75x and speedups of 24.48-38.58x with the same power constraint. MemSort's throughput is at least 4.86x higher than that of the recent FPGA-based sorting accelerator FANS. MemSort exhibits more than 11x throughput and 4.03x area efficiency, compared with the recent CiM-based sorting accelerator, RIME.
This paper presents a method of analyzing efficiency of tobacco automated sorting system and two optimal methods based on the results of analysis. In efficiency analysis, we create a definition-efficiency bottleneck a...
详细信息
ISBN:
(纸本)9781424415304
This paper presents a method of analyzing efficiency of tobacco automated sorting system and two optimal methods based on the results of analysis. In efficiency analysis, we create a definition-efficiency bottleneck as the criterion of efficiency judgement. Then based on bottleneck, we devise 2 kinds of optimal methods. One mends the system's sorting algorithm to fit the bottleneck;the other eliminates the bottleneck radically by changing the layout of sorting system. The first method improves system's sorting efficiency from 7500/h to 9500/h, while the second method can improve system's sorting efficiency above 12000/h.
Emerging persistent memory (PM, also termed as nonvolatile memory) technologies can promise large capacity, non-volatility, byte-addressability and DRAM-comparable access latency. Such amazing features have inspired a...
详细信息
ISBN:
(纸本)9783030731991;9783030732004
Emerging persistent memory (PM, also termed as nonvolatile memory) technologies can promise large capacity, non-volatility, byte-addressability and DRAM-comparable access latency. Such amazing features have inspired a host of PM-based storage systems and applications that store and access data directly in PM. sorting is an important function for many systems, but how to optimize sorting for PM-based systems has not been systematically studied yet. In this paper, we conduct extensive experiments for many existing sorting methods, including both conventional sorting algorithms adapted for PM and recently-proposed PM-friendly sorting techniques, on a real PM platform. The results indicate that these sorting methods all have drawbacks for various workloads. Some of the results are even counterintuitive compared to running on a DRAM-simulated platform in their papers. To the best of our knowledge, we are the first to perform a systematic study on the sorting issue for persistent memory. Based on our study, we propose an adaptive sorting engine, namely SmartSort, to optimize the sorting performance for different conditions. The experimental results demonstrate that SmartSort remarkably outperforms existing sorting methods in a variety of cases.
We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complex...
详细信息
We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is O(n(log23)) in contrast to O(n(2)) of standard insertion sort.
This paper presents a new approach for linear-time suffix sorting. It introduces a new sorting principle that can be used to build the first non-recursive linear-time suffix array construction algorithm named GSACA. A...
详细信息
High-resolution climate data O(1 km) at the catchment scale can be of great value to both hydrological modellers and end users, in particular for the study of extreme precipitation. While dynamical downscaling with co...
详细信息
High-resolution climate data O(1 km) at the catchment scale can be of great value to both hydrological modellers and end users, in particular for the study of extreme precipitation. While dynamical downscaling with convection-permitting models is a valuable approach for producing quality high-resolution O(1 km) data, its added value can often not be realized due to the prohibitive computational expense. Here we present a novel and flexible classification algorithm for discriminating between days with an elevated potential for extreme precipitation over a catchment and days without, so that dynamical downscaling to convection-permitting resolution can be selectively performed on high-risk days only, drastically reducing total computational expense compared to continuous simulations;the classification method can be applied to climate model data or reanalyses. Using observed precipitation and the corresponding synoptic-scale circulation patterns from reanalysis, characteristic extremal circulation patterns are identified for the catchment via a clustering algorithm. These extremal patterns serve as references against which days can be classified as potentially extreme, subject to additional tests of relevant meteorological predictors in the vicinity of the catchment. Applying the classification algorithm to reanalysis, the set of potential extreme days (PEDs) contains well below 10 % of all days, though it includes essentially all extreme days;applying the algorithm to reanalysis-driven regional climate simulations over Europe (12 km resolution) shows similar performance, and the subsequently dynamically downscaled simulations (2 km resolution) well reproduce the observed precipitation statistics of the PEDs from the training period. Additional tests on continuous 12 km resolution historical and future (RCP8.5) climate simulations, downscaled in 2 km resolution time slices, show the algorithm again reducing the number of days to simulate by over 90 % and performing con
Fluorescence-based detection has been commonly used in high-throughput screening (HTS) assays. Autofluorescent compounds, which can emit light in the absence of artificial fluorescent markers, often interfere with the...
详细信息
Fluorescence-based detection has been commonly used in high-throughput screening (HTS) assays. Autofluorescent compounds, which can emit light in the absence of artificial fluorescent markers, often interfere with the detection of fluorophores and result in false positive signals in these assays. This interference presents a major issue in fluorescence-based screening techniques. In an effort to reduce the time and cost that will be spent on prescreening of autofluorescent compounds, in silico autofluorescence prediction models were developed for selected fluorescence-based assays in this study. Five prediction models were developed based on the respective fluorophores used in these HTS assays, which absorb and emit light at specific wavelengths (excitation/emission): Alexa Fluor 350 (A350) (340 nm/450 nm), 7-amino-4-trifluoromethyl-coumarin (AFC) (405 nm/520 nm), Alexa Fluor 488 (A488) (480 nm/540 nm), Rhodamine (547 nm/598 nm), and Texas Red (547 nm/618 nm). The C5.0 rule-based classification algorithm and PubChem 2D chemical structure fingerprints were used to develop prediction models. To optimize the accuracies of these prediction models despite the highly imbalanced ratio of fluorescent versus nonfluorescent compounds presented in the collected data sets, oversampling and undersampling strategies were applied. The average final accuracy achieved for the training set was 97%, and that for the testing set was 92%. In addition, five external data sets were used to further validate the models. Ultimately, 14 representative structural features (or rules) were determined to efficiently predict autofluorescence in data sets containing both fluorescent and nonfluorescent compounds. Several cases were illustrated in this study to demonstrate the applicability of these rules.
Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to ...
详细信息
ISBN:
(纸本)1581133294
Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to its concrete subclasses. Comparison on objects is carried out via an abstract ordering strategy. This reduces code complexity and simplifies the analyses of the various concrete sorting algorithms. Performance measurements and visualizations can be added without modifying any code by utilizing the decorator design pattern. This object-oriented design not only provides the student a concrete way of unifying seemingly disparate sorting algorithms but also help him/her differentiate them at the proper level of abstraction.
Variable selection with supervised classification is currently an important tool for discriminating biological samples. In this paper, 15 supervised classification algorithms based on a support vector machine (SVM) we...
详细信息
Variable selection with supervised classification is currently an important tool for discriminating biological samples. In this paper, 15 supervised classification algorithms based on a support vector machine (SVM) were applied to discriminate Cryptococcus neoformans and Cryptococcus gattii fungal species using ATR-FTIR spectroscopy. These two fungal species of the Cryptococcus genus are the etiological agents of Cryptococcosis, which is an opportunistic or primary fungal infection with global distribution. This disease is potentially fatal, especially for immunocompromised patients, like those suffering from AIDS. The multivariate classification algorithms tested were based on principal component analysis (PCA), successive projections algorithm (SPA) and genetic algorithm (GA) as data reduction and variable selection methods, being coupled to a SVM with different kernel functions (linear, quadratic, 3rd order polynomial, radial basis function, and multilayer perceptron). Some of these algorithms achieved very successful classification rates for discriminating fungal species, with accuracy, sensitivity, and specificity equal to 100% using both SPA-SVM-polynomial and GA-SVM-polynomial algorithms. These results show the potential of such techniques coupled to ATR-FTIR spectroscopy as a rapid and non-destructive tool for classifying these fungal species.
A classification algorithm is presented that uses hidden Markov models (HMMs) to carry out recognition between three classes of targets: personnel, tracked vehicles and wheeled vehicles. It exploits the time-varying n...
详细信息
A classification algorithm is presented that uses hidden Markov models (HMMs) to carry out recognition between three classes of targets: personnel, tracked vehicles and wheeled vehicles. It exploits the time-varying nature of radar Doppler data in a manner similar to techniques used in speech recognition, albeit with a modified topology, to distinguish targets with different Doppler characteristics. The algorithm was trained and tested on real radar signatures of multiple examples of moving targets from each class, and the performance was shown to be invariant to target speed and orientation and was able to be generalised with respect to variants within a class.
暂无评论