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)
22-21
Our theoretical study concerns an urea-urease-based pH oscillator confined to giant lipid vesicles. Under suitable conditions, differential transport of urea and hydrogen ion across the unilamellar vesicle membrane periodically resets the pH clock that switches the system from acid to basic, resulting in self-sustained oscillations. We analyse the structure of the limit cycle, which controls the dynamics for giant vesicles and dominates the strongly stochastic oscillations in small vesicles of submicrometer size. To this end, we derive reduced models, amenable to analytic treatments, and show that the accuracy of predictions, including the period of oscillations, is highly sensitive to the choice of the reduction scheme. In particular, we suggest an accurate two-variable model and show its equivalence to a three-variable model that admits an interpretation in terms of a chemical reaction network. The accurate description of a single pH oscillator appears crucial for rationalizing experiments and understanding communication of vesicles and synchronization of rhythms.
21-36
We study the formation of trails in populations of self-propelled agents that make oriented deposits of pheromones and also sense such deposits to which they then respond with gradual changes of their direction of motion. Based on extensive off-lattice computer simulations aiming at the scale of insects, e.g., ants, we identify a number of emerging stationary patterns and obtain qualitatively the non-equilibrium \add{state} diagram of the model, spanned by the strength of the agent--pheromone interaction and the number density of the population. In particular, we demonstrate the spontaneous formation of persistent, macroscopic trails, and highlight some behaviour that is consistent with a dynamic phase transition. This includes a characterisation of the mass of system-spanning trails as a potential order parameter. We also propose a dynamic model for a few macroscopic observables, including the sub-population size of trail-following agents, which captures the early phase of trail formation.
20-17
The aim of this thesis is to deepen our understand of how
IDA* heuristics influence the number of nodes expanded during
search. To this end, we develop Korf's formula for the number
of expanded nodes into a heuristic quality η which
expresses the quality of a heuristic function as a constant factor
on the number of expanded nodes, independent of a particular problem
instance.
We proceed to show how to compute η for some common kinds of
heuristics and how to estimate η by means of a random sample for
arbitrary heuristics. Using the value of η for some concrete
examples, we then inspect for which parts of the search space the
values of h(v) are particularly critical to the performance of the
heuristic, allowing us to build better heuristics for future problems.
This report originally appeared as a master thesis at Humboldt
University of Berlin.
19-52
MPI passive target synchronization offers exclusive and shared locks. These are the building blocks for the implementation of applications with Readers & Writers semantic, like for example distributed hash tables. This paper discusses the implementation of MPI passive target synchronization on a non-cache-coherent multicore, the Intel Single-Chip Cloud Computer. The considered algorithms differ in their communication style (message based versus shared memory), their data structures (centralized versus distributed) and their semantics (with/without Writer preference). It is shown that shared memory approaches scale very well and deliver good performance, even in absence of cache coherence.
18-62
The growing discrepancy between CPU computing power and memory bandwidth drives more and more numerical algorithms into a bandwidth-
bound regime. One example is the overlapping Schwarz smoother, a highly effective building block for iterative multigrid solution of elliptic equations with higher order finite elements. Two options of reducing the required
memory bandwidth are sparsity exploiting storage layouts and representing matrix entries with reduced precision in floating point or fixed point
format. We investigate the impact of several options on storage demand and contraction rate, both analytically in the context of subspace correction methods and numerically at an example of solid mechanics. Both perspectives agree on the favourite scheme: fixed point representation of Cholesky factors in nested dissection storage.
17-78
Comets display with decreasing solar distance an increased emission of gas and dust particles, leading to the formation of the coma and tail. Spacecraft missions provide insight in the temporal and spatial variations of the dust and gas sources located on the cometary nucleus. For the case of comet 67P/Churyumov-Gerasimenko (67P/C-G), the long-term obser- vations from the Rosetta mission point to a homogeneous dust emission across the entire illuminated surface. Despite the homogeneous initial dis- tribution, a collimation in jet-like structures becomes visible. We propose that this observation is linked directly to the complex shape of the nucleus and projects concave topographical features into the dust coma. To test this hypothesis, we put forward a gas-dust description of 67P/C-G, where gravitational and gas forces are accurately determined from the surface mesh and the rotation of the nucleus is fully incorporated. The emerging jet-like structures persist for a wide range of gas-dust interactions and show a dust velocity dependent bending.
17-64
Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them.
This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances.
PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.
17-59
This report aims to explain and extend pattern databases as a tool in finding optimal solutions to combination puzzles. Using sliding tile puzzles as an example, an overview over techniques to construct and use pattern databases is given, analysed, and extended. As novel results, zero aware additive pattern databases and PDB catalogues are introduced. This report originally appeared as a bachelor thesis at Humboldt University of Berlin under the title Notes on the Construction of Tablebases.
16-48
The effectiveness of ahead-of-time compiler optimization heavily depends on the amount of available information at compile time. Input-specific information that is only available at runtime cannot be used, although it often determines loop counts, branching predicates and paths, as well as memory-access patterns. It can also be crucial for generating efficient SIMD-vectorized code. This is especially relevant for the many-core architectures paving the way to exascale computing, which are more sensitive to code-optimization. We explore the design-space for using input-specific information at compile-time and present KART, a C++ library solution that allows developers to compile, link, and execute code (e.g., C, C++ , Fortran) at application runtime. Besides mere runtime compilation of performance-critical code, KART can be used to instantiate the same code multiple times using different inputs, compilers, and options. Other techniques like auto-tuning and code-generation can be integrated into a KART-enabled application instead of being scripted around it. We evaluate runtimes and compilation costs for different synthetic kernels, and show the effectiveness for two real-world applications, HEOM and a WSM6 proxy.
16-26
The Rosetta probe around comet 67P/Churyumov-Gerasimenko (67P) reveals an anisotropic dust distribution of the inner coma with jet-like structures. The physical processes leading to jet formation are under debate, with most models for cometary activity focusing on localised emission sources, such as cliffs or terraced regions. Here we suggest, by correlating high-resolution simulations of the dust environment around 67P with observations, that the anisotropy and the background dust density of 67P originate from dust released across the entire sunlit surface of the nucleus rather than from few isolated sources. We trace back trajectories from coma regions with high local dust density in space to the non-spherical nucleus and identify two mechanisms of jet formation: areas with local concavity in either two dimensions or only one. Pits and craters are examples of the first case, the neck region of the bilobed nucleus of 67P for the latter one. The conjunction of multiple sources in addition to dust released from all other sunlit areas results in a high correlation coefficient (∼0.8) of the predictions with observations during a complete diurnal rotation period of 67P.
15-30
Time series classification mimics the human understanding of similarity. When it comes to larger datasets, state of the art classifiers reach their limits in terms of unreasonable training or testing times. One representative example is the 1-nearest-neighbor DTW classifier (1-NN DTW) that is commonly used as the benchmark to compare to and has several shortcomings: it has a quadratic time and it degenerates in the presence of noise. To reduce the computational complexity lower bounding techniques or recently a nearest centroid classifier have been introduced. Still, execution times to classify moderately sized datasets on a single core are in the order of hours. We present our Bag-Of-SFA-Symbols in Vector Space (BOSS VS) classifier that is robust and accurate due to invariance to noise, phase shifts, offsets, amplitudes and occlusions. We show that it is as accurate while being multiple orders of magnitude faster than state of the art classifiers. Using the BOSS VS allows for mining massive time series datasets and real-time analytics.
15-29
Amalgamated graph transformation allows to define schemes of rules
coinciding in common core activities and differing over additional parallel independent
activities. Consequently, a rule scheme is specified by a kernel rule and a set of extending multi-rules forming an interaction scheme. Amalgamated
transformations have been increasingly used in various modeling contexts.
Critical Pair Analysis (CPA) can be used to show local confluence of graph transformation
systems. It is an open challenge to lift the CPA to amalgamated graph transformation systems, especially since infinite many pairs of amalgamated rules
occur in general. As a first step towards an efficient local confluence analysis of
amalgamated graph transformation systems, we show that the analysis of a finite
set of critical pairs suffices to prove local confluence.
15-17
To achieve high floating point compute performance, modern processors draw on short vector SIMD units, as found e.g. in Intel CPUs (SSE, AVX1, AVX2 as well as AVX-512 on the roadmap) and the Intel Xeon Phi coprocessor, to operate an increasingly larger number of operands simultaneously. Making use of SIMD vector operations therefore is essential to get close to the processor’s floating point peak performance.
Two approaches are typically used by programmers to utilize the vector units: compiler driven vectorization via directives and code annotations, and manual vectorization by means of SIMD intrinsic operations or assembly.
In this paper, we investigate the capabilities of the current Intel compiler (version 15 and later) to generate vector code for non-trivial coding patterns within loops. Beside the more or less uniform data-parallel standard loops or loop nests, which are typical candidates for SIMDfication, the occurrence of e.g. (conditional) function calls including branching, and early returns from functions may pose difficulties regarding the effective use of vector operations. Recent improvements of the compiler's capabilities involve the generation of SIMD-enabled functions. We will study the effectiveness of the vector code generated by the compiler by comparing it against hand-coded intrinsics versions of different kinds of functions that are invoked within innermost loops.
15-05
With the growing number of hardware components and the increasing software complexity in the upcoming exascale computers, system failures will become the norm rather than an exception for long-running applications. Fault-tolerance can be achieved by the creation of checkpoints during the execution of a parallel program. Checkpoint/Restart (C/R) mechanisms allow for both task migration (even if there were no hardware faults) and restarting of tasks after the occurrence of hardware faults. Affected tasks are then migrated to other nodes which may result in unfortunate process placement and/or oversubscription of compute resources. In this paper we analyze the impact of unfortunate process placement and oversubscription of compute resources on the performance and scalability of two typical HPC application workloads, CP2K and MOM5. Results are given for a Cray XC30/40 with Aries dragonfly topology. Our results indicate that unfortunate process placement has only little negative impact while oversubscription substantially degrades the performance. The latter might be only (partially) beneficial when placing multiple applications with different computational characteristics on the same node.
14-23
The applicability of accelerators is limited by the attainable speed-up for the offloaded computations and by the offloading overheads. While GPU programming models like CUDA and OpenCL only allow to optimise the application code and its speed-up, the available low-level APIs for the Intel Xeon Phi provide opportunity to address the overheads, too. This work presents an Heterogeneous Active Message (HAM) layer that minimises software overheads for offloading on Intel’s Xeon Phi. It provides the basis for an offload API with similar semantics as the Intel Language Extensions for Offload (LEO). In contrast to LEO, HAM works within the C++ language and needs no additional compiler support. We evaluated HAM on top of SCIF and MPI as communication backends. While the SCIF backend offers the best performance, the MPI backend allows for inter-node offloads which are not possible with other offload solutions.
Benchmark results show that the cost for offloading a function call can be
decreased by a factor up to 18 compared with LEO.
14-19
Small-scale computations usually cannot fully utilize the compute capabilities of modern GPGPUs. With the Fermi GPU architecture Nvidia introduced the concurrent kernel execution feature allowing up to 16 GPU kernels to execute simultaneously on a shared GPU device for a better utilization of the respective resources. Insufficient scheduling capabilities in this respect, however, can significantly reduce the theoretical concurrency level. With the Kepler GPU architecture Nvidia addresses this issue by introducing the Hyper-Q feature with 32 hardware managed work queues for concurrent kernel execution.
We investigate the Hyper-Q feature within heterogeneous workloads with multiple concurrent host threads or processes offloading computations to the GPU each.
By means of a synthetic benchmark kernel and a hybrid parallel CPU-GPU real-world application, we evaluate the performance obtained with Hyper-Q on GPU and compare it against a kernel reordering mechanism introduced by the authors for the Fermi architecture.
14-15
The third generation of the North German Supercomputing Alliance (HLRN) compute and storage facilities comprises a Cray XC30 architecture with exclusively Intel Ivy Bridge compute nodes. In the second phase, scheduled for November 2014, the HLRN-III configuration will undergo a
substantial upgrade together with the option of integrating
accelerator nodes into the system. To support the decision-making process, a four-node Intel Xeon Phi cluster is integrated into the present HLRN-III infrastructure at ZIB. This integration includes user/project management, file system access and job management via the HLRN-III batch system. For selected workloads, in-depth analysis, migration and optimization work on Xeon Phi is in progress. We will report our experiences and lessons learned within the Xeon Phi installation and integration
process. For selected examples, initial results of the application evaluation on the Xeon Phi cluster platform will be discussed.
13-21
The performance of heuristic search algorithms depends crucially on the effectiveness of the heuristic. A pattern database (PDB) is a powerful heuristic in the form of a pre-computed lookup table. Larger PDBs provide better bounds and thus allow more cut-offs in the search process. Today, the largest PDB for the 24-puzzle is a 6-6-6-6 PDB with a size of 486 MB.
We created 8-8-8, 9-8-7 and 9-9-6 PDBs that are three orders of magnitude larger (up to 1.4 TB) than the 6-6-6-6 PDB. We show how to compute such large PDBs and we present statistical and empirical data on their efficiency. The largest single PDB gives on average an 8-fold improvement over the 6-6-6-6 PDB. Combining several large
PDBs gives on average an 12-fold improvement.
12-23
Scheduling algorithms for heterogeneous platforms make scheduling decisions based on several metrics. One of these metrics is the amount of data to be transferred from and to the accelerator. However, the automated determination of this metric is not a simple task. A few schedulers and runtime systems solve this problem by using regression models, which are imprecise though. Our novel approach for the determination of data volumes removes this limitation and thus provides a solution to obtain exact information.
12-22
Attributes are an important concept for modeling data in practical applications. Up to now there is no adequate way to define attributes for different kinds of models used in M-adhesive transformation systems, which are a special kind of graph transformation systems based on M-adhesive categories. Especially a proper representation and definition of attributes and their values as well as a suitable handling of the data does not fit well with other graph transformation formalisms.
In this paper, we propose a new method to define attributes in a natural, but still formally precise and widely applicable way. We define a new kind of adhesive category, called W-adhesive, that can be used for transformations of attributes, while the underlying models are still M-adhesive ones. As a result, attributed models can be used as they are intended to be, but with a formal background and proven well-behavior.
10-02
Applications which need exclusive access to a shared resource in distributed systems require a fault-tolerant and scalable mechanism to coordinate this exclusive access. Examples of such applications include distributed file systems and master/slave data replication. We present Flease, an algorithm for decentralized and fault-tolerant lease coordination in distributed systems. Our algorithm allows the processes competing for a resource to coordinate exclusive access through leases among themselves without a central component. The resulting system easily scales with an increasing number of nodes and resources. We prove that Flease ensures exclusive access, i.e. guarantees that there is at most one valid lease at any time.
09-34
Transactional DHT Algorithms
(2009)
We present a framework for transactional data access on data stored in a DHT. It allows to atomically read and write items and to run distributed transactions consisting of a sequence of read and write operations on the items. Items are symmetrically replicated in order to achieve durability of data stored in the SON. To provide availability of items despite the unavailability of some replicas, operations on items are quorum-based. They make progress as long as a majority of replicas can be accessed. Our framework processes transactions optimistically with an atomic commit protocol that is based on Paxos atomic commit. We present algorithms for the whole framework with an event based notation. Additionally we discuss the problem of lookup inconsistencies and its implications on the one-copy serializability property of the transaction processing in our framework.
09-28
Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.
08-54
We study performance and scaling of the Berlin Quantum Chromodynamics Program (BQCD) on the SGI Altix 4700 at Leibniz Supercomputing Centre (LRZ). We employ different communication methods (MPI, MPI with two OpenMP threads per process, as well as the shmem library) and run the MPI version on the two types of nodes of that machine. For comparison with other machines we made performance measurements on an IBM p690 cluster and a Cray XT4.
07-48
The latest machine generation installed at supercomputer centres in Germany offers a peak performance in the tens of Tflop/s range. We study performance and scaling of our quantum chromodynamics simulation programme BQCD that we obtained on two of these machines, an IBM Blue Gene/L and an SGI Altix 4700. We compare the performance of Fortran/MPI code with assembler code. The latter allows to exploit concurrency at more levels, in particular in overlapping communication and computation as well as prefetching data from main memory.
07-43
Die Arbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewährleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenläufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen.
07-42
Berlin als Stadtstaat ist Kommune und Land der Bundesrepublik zugleich und Standort vieler renommier-ter Wissenschafts- und Kultureinrichtungen. In enger Zusammenarbeit der Wissenschaftseinrichtungen mit dem IT-Dienstleistungszentrum Berlin (ITDZ, ehemals Landesbetrieb für Informationstechnik), der für die Behörden Berlins zuständigen Einrichtung, wurde seit 1993 ein landeseigenes Glasfasernetz mit einer derzeitigen Länge von 856 km Glasfaserkabel (je Kabel bis zu 144 Einzelfasern) zur gemeinsamen Nutzung von Wissenschaft und Verwaltung errichtet und weiter ausgebaut. 1994 erfolgte der offizielle Start des Berliner Wissenschaftsnetzes BRAIN (Berlin Research Area Information Network), als durch einen Beschluss des Senats von Berlin die Nutzung des landeseigenen Glasfasernetzes durch die Wissen-schaftseinrichtungen festgeschrieben wurde. Bereits 1995 wurden durch die Wissenschaftseinrichtungen auf diesem Glasfasernetz die ersten sieben Anschlüsse in ATM-Technik (Classical BRAIN-ATM) in Betrieb genommen, 1999 wurden anschließend auch erste Strecken in Ethernet-Technik (Classical BRAIN-GE) betrieben. Diese heterogenen Netze mit unterschiedlichen Netzgeräten wurden dezentral von den Netzadministratoren der beteiligten Einrichtungen nach globalen Absprachen betreut. Die dezentrale Administration erschwerte das Management und die Erweiterungen der Gesamtnetze. Basierend auf den vorliegenden Erfahrungen vereinbarten die Berliner Wissenschaftseinrichtungen, ein technisch neues Verbundnetz in Gigabit-Ethernet-Technik mit einheitlichen Geräten und einem zentralen Netzwerkmana-gement aufzubauen und zu betreiben. Seit November 2003 betreibt BRAIN auf dem landeseignen Glasfasernetz ein auf MPLS-Technik basie-rendes Gigabit-Ethernet-Netz, das „BRAIN-Verbundnetz“, mit den Diensten LAN-to-LAN-Kopplung der Einrichtungen, regionaler IP-Verkehr, Übergang zum Verwaltungsnetz und WiN-Backup. Das BRAIN-Verbundnetz löste die dezentral betreuten Vorläufernetze komplett ab. Von den derzeit 27 BRAIN-Teilnehmern nutzen 24 Einrichtungen an 53 in der Stadt verteilten Standorten die Dienste des BRAIN-Verbundnetzes, 18 Standorte sind mit 1000 Mbit/s und 35 Standorte mit 100 Mbit/s angeschlossen. Für verteilte Standorte einer Einrichtung besteht zudem die Möglichkeit, diese über dedizierte Fasern oder Bandbreiten miteinander zu vernetzen. Seit dem 2. Quartal 2007 wird im Rahmen eines Pilotprojekts der Nutzen eines zentral gemanagten Fibre Channel-Netzwerks "BRAIN-SAN" ermittelt, um Möglichkeiten einer verteilten Datenhaltung der Berliner Hochschulen und wissenschaftlichen Einrichtungen zu schaf-fen. Zusätzlich zu den vorgenannten Diensten nutzt der DFN-Verein die BRAIN-Struktur für die Verbindun-gen der X-WiN-Kernnetzknoten in Berlin und Potsdam untereinander und für Zugangsleitungen zu den Anwendern. Mit Stand 2007 nutzt das Berliner Wissenschaftsnetz BRAIN vom landeigenen Glasfasernetz 2100 km Einzelfasern und verbindet insgesamt 43 Einrichtungen (BRAIN-Teilnehmer und DFN-Anwender) aus Wissenschaft, Bildung und Kultur mit 129 Standorten. Der Betrieb von BRAIN wird im wesentlichen durch seine Nutzer finanziert. Das Land Berlin trägt aller-dings pauschal die überwiegenden Kosten für die Wartung des Glasfasernetzes, soweit es vom ITDZ be-reit gestellt wird. Zentrales Planungs- und Steuerungsorgan für BRAIN ist die von der Senatsverwaltung für Bildung, Wis-senschaft und Forschung eingerichtete BRAIN-Planungsgruppe. Sie besteht aus Mitarbeitern der Rechen-zentren der drei Berliner Universitäten und des ZIB. Nach außen wird BRAIN in rechtlicher und wirtschaftlicher Hinsicht treuhänderisch vom ZIB vertreten, die BRAIN-Geschäftsstelle befindet sich ebenfalls im ZIB.
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.
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.
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.
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.
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.
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}.
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.
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.