ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (37)
Has Fulltext
- yes (37)
Is part of the Bibliography
- no (37)
Keywords
- DHT (3)
- Paxos (3)
- GPGPU (2)
- MPI (2)
- 67p (1)
- Active message (1)
- Algorithms (1)
- Bioinformatics (1)
- Classification (1)
- Concurrent Kernel Execution (1)
Institute
- Distributed Algorithms and Supercomputing (37) (remove)
13-16
Dieser Bericht beschreibt in allgemein
verständlicher Form die Struktur der
Datenhaltung im Zuse‐Institut Berlin (ZIB) und
die aktuell verwendeten Strategien im Umgang
mit immer stärker wachsenden Datenmengen,
sowie der Herausforderung der Speicherung
unwiederbringlicher Daten über im Grunde
unbegrenzte Zeit.
13-46
Current programming models for heterogeneous devices with disjoint physical memory spaces require explicit allocation of device memory and explicit data transfers. While it is quite easy to manually implement these operations for linear data objects like arrays, this task becomes more difficult for non-linear objects, e.g. linked lists or multiple inherited classes. The difficulties arise due to dynamic memory requirements at run-time and the dependencies between data structures. In this paper we present a novel method to build a graph-based static data type description which is used to create code for injectable functions that automatically determine the memory footprint of data objects at run-time. Our approach is extensible to implement automatically generated optimized data transfers across physical memory spaces.
13-44
Simulations of the critical Ising model by means of local update algorithms suffer from critical slowing down. One way to partially compensate for the influence of this phenomenon on the runtime of simulations is using increasingly faster and parallel computer hardware. Another approach is using algorithms that do not suffer
from critical slowing down, such as cluster algorithms. This paper reports on the Swendsen-Wang multi-cluster algorithm on Intel Xeon Phi coprocessor 5110P, Nvidia Tesla M2090 GPU, and x86
multi-core CPU. We present shared memory versions of the said algorithm for the simulation of the two- and three-dimensional Ising model. We use a combination of local cluster search and global label reduction by means of atomic hardware primitives. Further, we
describe an MPI version of the algorithm on Xeon Phi and CPU, respectively. Significant performance improvements over known im
plementations of the Swendsen-Wang algorithm are demonstrated.
02-06
\textsf{\itshape{GuiGen}} is a comprehensive set of tools for creating customized graphical user interfaces (GUIs). It draws from the concept of computing portals, which are here seen as interfaces to application-specific computing services for user communities. While \textsf{\itshape{GuiGen}} was originally designed for the use in computational grids, it can be used in client/server environments as well. Compared to other GUI generators, \textsf{\itshape{GuiGen}} is more versatile and more portable. It can be employed in many different application domains and on different target platforms. With \textsf{\itshape{GuiGen}}, application experts (rather than computer scientists) are able to create their own individually tailored GUIs.
02-52
Global grid environments do not only provide massive aggregated computing power but also an unprecedented amount of distributed storage space. Unfortunately, dynamic changes caused by component failures, local decisions, and irregular data updates make it difficult to efficiently use this capacity. In this paper, we address the problem of improving data availability in the presence of unreliable components. We present an analytical model for determining an optimal combination of distributed replica catalogs, catalog sizes, and replica servers. Empirical simulation results confirm the accuracy of our theoretical analysis. Our model captures the characteristics of highly dynamic environments like peer-to-peer networks, but it can also be applied to more centralized, less dynamic grid environments like the European {\em DataGrid}.
03-06
While attribute-value pairs are a popular method to name objects, information retrieval from those attribute-based namespaces is not an easy task. The user has to recall correct attribute names and values and master the syntax and semantics of query formulation. This paper describes hierarchical structures in attribute-based namespaces, shows how to extract them efficiently and evaluates the quality of these structures in an user experiment. It proposes an user interface for browsing attribute-named object sets which makes this task resemble todays file-system browsers and compares the usability of this interface to normal form-based methods in an user study.
05-40
\newcommand{\chordsharp}{Chord$^\##$} Data lookup is a fundamental problem in peer-to-peer systems: Given a key, find the node that stores the associated object. Chord and other P2P algorithms use distributed hash tables (DHTs) to distribute the keys and nodes evenly across a logical ring. Using an efficient routing strategy, DHTs provide a routing performance of $O (\log N)$ in networks of $N$ nodes. While the routing performance has been shown to be optimal, the uniform key distribution makes it impossible for DHTs to support range queries. For range queries, consecutive keys must be stored on lo gically neighboring nodes. In this paper, we present an enhancement of Chord that eliminates the hash function while keeping the same routing performance. The resulting algorithm, named \chordsharp{}, provides a richer function ality while maintaining the same complexity. In addition to Chord, \chordsharp{} adapts to load imbalance.
06-24
THESEUS, the ZIB threading environment, is a parallel implementation of a protein threading based on a multi-queued branch-and-bound optimal search algorithm to find the best sequence-to-structure alignment through a library of template structures. THESEUS uses a template core model based on secondary structure definition and a scoring function based on knowledge-based potentials reflecting pairwise interactions and the chemical environment, as well as pseudo energies for homology detection, loop alignment, and secondary structure matching. The threading core is implemented in C++ as a SPMD parallization architecture using MPI for communication. The environment is designed for generic testing of different scoring functions, e.g. different secondary structure prediction terms, different scoring matrices and information derived from multiple sequence alignments. A validaton of the structure prediction results has been done on the basis of standard threading benchmark sets. THESEUS successfully participated in the 6th Critical Assessment of Techniques for Protein Structure Prediction (CASP) 2004.
06-44
During the last few years more and more functionalities of RNA have been discovered that were previously thought of being carried out by proteins alone. One of the most striking discoveries was the de tection of microRNAs, a class of noncoding RNAs that play an important role in post-transcriptional gene regulation. Large-scale analyses are needed for the still increasingly growing amount of sequen ce data derived from new experimental technologies. In this paper we present a framework for the detection of the distinctive precursor structure of microRNAS that is based on the well-known Smith-Wat erman algorithm and various filtering steps. We conducted experiments on real genomic data and we found several new putative hits for microRNA precursor structures.
07-23
We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.