1,720,994 research outputs found
K-model: A new computational model for stream processors
No full textWe introduce K-model, a computational model to evaluate the algorithms designed for graphic processors, and other architectures adhering to the stream programming model. We address the lack of a formal complexity model that properly accounts for memory contention, address coalescing in memory accesses, or the serial control of instruction flows. We study the impact of K-model rules on algorithm design. We devise a coalesced and low contention data access technique for Batcher's networks, and we evaluate the effectiveness of this technique within our K-model. To evaluate the benefits in using K-model in evaluating solutions for streaming architectures, we compare the complexity of a sorting network built using our technique, and quicksort. Although in theory quicksort is more efficient than bitonic sort, empirically, our bitonic sorting network has been shown to be faster than the state-of-the-art implementation of quicksort on graphics processing units (GPUs). We use our K-model to prove that this observation should generally hold. As a side result, our technique to perform a Batcher's network on GPUs improves the performance of one the fastest comparison-based solution for integers sorting. © 2010 IEEE
Sorting on GPUs for large scale datasets: A thorough comparison
No full textAlthough sort has been extensively studied in many research works, it still remains a challenge in particular if we consider the implications of novel processor technologies such as manycores (i.e. GPUs, Cell/BE, multicore, etc.). In this paper, we compare different algorithms for sorting integers on stream multiprocessors and we discuss their viability on large datasets (such as those managed by search engines). In order to fully exploit the potentiality of the underlying architecture, we designed an optimized version of sorting network in the K-model, a novel computational model designed to consider all the important features of many-core architectures. According to K-model, our bitonic sorting network mapping improves the three main aspects of many-core architectures, i.e. the processors exploitation, and the on-chip/off-chip memory bandwidth utilization. Furthermore we are able to attain a space complexity of Θ(1). We experimentally compare our solution with state-of-the-art ones (namely, Quicksort and Radixsort) on GPUs. We also compute the complexity in the K-model for such algorithms. The conducted evaluation highlight that our bitonic sorting network is faster than Quicksort and slightly slower than radix, yet being an in-place solution it consumes less memory than both algorithms
Sorting using bitonic network with CUDA
No full textNovel"manycore" architectures, such as graphics processors, are high-parallel and high-performance shared-memory ar- chitectures [7] born to solve specific problems such as the graphical ones. Those architectures can be exploited to solve a wider range of problems by designing the related algorithm for such architectures. We present a fast sorting algorithm implementing an efficient bitonic sorting network. This algorithm is highly suitable for information retrieval applications. Sorting is a fundamental and universal prob- lem in computer science. Even if sort has been extensively addressed by many research works, it still remains an inter- esting challenge to make it faster by exploiting novel tech- nologies. In this light, this paper shows how to use graph- ics processors as coprocessors to speed up sorting while al- lowing CPU to perform other tasks. Our new algorithm exploits a memory-efficient data access pattern maintain- ing the minimum number of accesses to the memory out of the chip. We introduce an efficient instruction dispatch mechanism to improve the overall sorting performance. We also present a cache-based computational model for graph- ics processors. Experimental results highlight remarkable improvements over prior CPU-based sorting methods, and a significant improvement over previous GPU-based sorting algorithms
Glue containment and anastomosis reinforcement in repair of aortic dissection
No full textIn operations for aortic dissection anastomotic bleeding or secondary anastomosis dehiscence are common problems. The advent of Gelatin-resorcin- formaldehyde-glutaraldehyde (GRF) biologic glue has ameliorated type A dissection operative management. Glue containment is mandatory since detrimental effects of glue migration are described. We herein present a simple technique of anastomosis reinforcement and glue containment that helps in overcoming these complications
Emergency cannulation for proximal perfusion in descending thoracic aorta procedures
No full textAcute cardiac failure during descending thoracic aorta operations, although rare, may have catastrophic consequences. Under these circumstances, the use of partial veno arterial bypass is advantageous, allowing an assisted perfusion of both proximal and distal circulation districts. Traditionally, the ascending aorta or the aortic arch are the preferred sites of cannulation for proximal arterial reinfusion, but some limitations, such as extensive calcifications or extreme fragility of these segments, may hamper or at least delay this action. Herein, we describe a simple technique for rapid cannulation of proximal aorta in emergency circumstances
A multi-criteria job scheduling framework for large computing farms
No full textIn this paper, we propose a new multi-criteria job scheduler for scheduling a continuous stream of batch jobs on large-scale computing farms. Our solution, called Convergent Scheduler, exploits a set of heuristics that drives the scheduler in taking decisions. Each heuristics manages a specific problem constraint, and contributes to compute a value that measures the degree of matching between a job and a machine. Scheduling choices are taken both to meet the Quality of Service requested by the submitted jobs and to optimize the usage of software and hardware resources. In order to validate the scheduler we propose, it has been compared versus two common job scheduling algorithms: Easy and Flexible backfilling. Convergent Scheduler demonstrated to be able to compute good assignments that allow a better exploitation of resources with respect to the other algorithms. Moreover, it has a simple modular structure that makes simple its extension and customization to meet the service goal of an installation. (C) 2012 Elsevier Inc. All rights reserved
A Multi-criteria Job Scheduling Framework for Large Computing Farms
No full textIn this paper, we propose a multi-criteria job scheduler for scheduling a continuous stream of batch jobs on largescale computing farms, called Convergent Scheduling 2.0 (CS 2.0), which is an enhancement of the scheduler described in. CS 2.0 exploits a set of heuristics that drive the scheduler in taking decisions. Each heuristics manages a specific constraint, and contributes to compute the measurement of the matching degree between a job and a machine. Scheduling choices are taken both to meet the QoS requested by the submitted jobs and to optimize the exploitation of hardware and software resources. In order to validate CS 2.0, we compared it versus two common job scheduling algorithms: Easy and Flexible backfilling. CS 2.0 demonstrated to be able to compute good assignments that allow a better exploitation of resources with respect to the other algorithms
Dramatic improvement of LV function after coronary sinus thromboembolectomy
No full textWe present the case of a 79-year-old man suffering from chronic atrial fibrillation, severe left ventricular dysfunction, massive right atrial thrombosis, and pulmonary hypertension. Complete coronary sinus thrombosis was found incidentally during preoperative screening. Successful coronary sinus, right atrial, and pulmonary operative embolectomy was followed soon after by a dramatic improvement of cardiac performance; the patient's left ventricular function recovery, in particular, suggests that cardiac venous system played an important role in the genesis of myocardial impairment. (C) 2000 by The Society of Thoracic Surgeons
Efficient diversification of search results using query logs
No full textWe study the problem of diversifying search results by exploiting the knowledge mined from query logs. Our proposal exploits the presence of different "specializations" of queries in query logs to detect the submission of ambiguous/faceted queries, and manage them by diversifying the search results returned in order to cover the different possible interpretations of the query. We present an original formulation of the results diversification problem in terms of an objective function to be maximized that admits the finding of an optimal solution in linear time. © 2011 Authors
- …
