Thesis: Shortest-path algorithm via CUDA

Graphics Processor Unit (GPU) are general purpose stream processor capable of very high computation and data throughput. In certain applications requiring massive vector operations, this can yield several orders of magnitude higher performance than a conventional CPU.

This task comprises of parallel implementation of Floyd-Warshall algorithm using CUDA. Floyd-Warshall algorithm is used to find shortest path in weighted graph. This task should be implemented by matrix-matrix multiplication approach and using CUBLAS library functions (if possible).

The design has to be optimized in terms of throughput and latency requirements.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Converting OpenCL into CUDA

Compute Unified Device Architecture (CUDA) is mature tool for developing high performance scientific applications on the GPU. OpenCL is open standard for cross-platform, parallel programming of heterogeneous processing systems which proposes a model which maps well to contemporary GPU architectures and a GPU programming model that bears close similarities to CUDA. OpenCL has attracted vendor support, with implementations available from NVIDIA, AMD , Apple and IBM. A tool for porting CUDA program to OpenCL called SWAN is already developed.

This task comprises porting of OpenCL program to CUDA and to test performance of application on OpenCL and on CUDA platform after porting. The design has to be optimized in terms of throughput and latency requirements of the system.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Implementation of CUBTAS library

Basic Linear Algebra Subprograms (BLAS) is a de facto application programming interface standard for publishing libraries to perform basic linear algebra operations such as vector and matrix multiplication. BLAS functionality is divided into three levels.

1. Vector operations
2. Matrix-Vector operations
3. Matrix-Matrix Operations

NVIDIA has implemented a similar library, called CUBLAS (Compute Unified Basic Linear Algebra Subprograms), for parallel programming on GPUs. The task is to implement a new library CUBTAS (Compute Unified Basic Tropical Algebra Subprograms) which performs similar operations to CUBLAS but using tropical algebra (min-plus algebra).

The design has to be optimized in terms of throughput and latency requirements of the system.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Parallel implementation of algorithm for phylogeny (ClustalW)

Sequence alignment is the fundamental operation in molecular biology for comparing bio molecular sequences to identify regions of similarity that consequences of structural, functional, or evolutionary relationships. ClustalW is a progressive alignment algorithm for multiple sequence alignment.

• Step 1: Determine all pairwise alignment between sequences and determine degrees of similarity between each pair.
• Step 2: Construct a guide tree.

• Step 3: Combine the alignments starting from the most closely related groups to the most distantly related groups, using the “once a gap always a gap” rule.

Graphics Processor Unit (GPU) are general purpose stream processor capable of very high computation and data throughput. In certain applications requiring massive vector operations, this can yield several orders of magnitude higher performance than a conventional CPU.

This work comprises of parallel implementation of ClustalW algorithm using CUDA. The resulting implementation design has to be optimized in terms of throughput and latency requirements.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Living as Machine?

This is the title of the new book of Klaus Mainzer (Mentis Verlag, Paderborn, 2010, 274 p.) that I got the other day. Mainzer's view is that of a unified theory of complex dynamical systems which is based on the assumption that all dynamic processes can be described by a computer program. This view embraces systems biology, artificial intelligence, and cyber physical systems. At the end, humans will be able to communicate with thinking machines and will merge into a single super-organism.

Students Wanted

We look for students who want to prepare a thesis in one of the following areas:

• Computational Intelligence: simulation of swarm behavior,
• Light-Weight Cryptography: security protocol for RFID,
• General Purpose Graphics Card Processing (GPGPU): dynamic programming algorithms on graphics card processor (GPU),
• Algebraic Coding: Gröbner bases for linear codes.

In these areas, we have contributed by recent journal publications.

Cooperative thesis:

• Logistics: data management and optimization (Prof. Pawellek).

External thesis:

• Efficient reconfiguration of aircraft cabin by using intelligent components (Airbus).

RFID-Protokolle für den Schlüsselaustausch mittels Permutation Parity Machines

Techniken zur Identifizierung und Datenübertragung mittels RFID (Radio Frequency IDentification) finden zunehmend Verbreitung im Alltag. Für die Übertragung von privaten Daten ist die Sicherung der Kommunikation gegen unautorisiertes Mithören von großer Bedeutung. Selbst wenn die Reichweite der Verbindung zwischen Chipkarte und Lesegerät stark begrenzt ist, etwa 10 cm, ist ein passives Mithören auf größere Entfernungen durchaus möglich.

Die Kommunikationsstrecke kann durch symmetrische oder asymmetrische Kryptoverfahren gesichert werden. Allerdings ist die Leistungsfähigkeit heutiger Chipkarten oftmals nicht ausreichend, um sichere symmetrische Schlüsselaustausch-Verfahren , etwa Diffie-Hellman, zu implementieren, während asymmetrische Verfahren einer Infrastruktur für die Zertifizierung bedürfen.

In der Arbeit wird ein Verfahren für den Schlüsselaustausch vorgeschlagen, das auf neuronalen Netzen, den so genannten Permutation Parity Machines (PPMs), beruht. Die PPM wurde als Binärversion der Tree Parity Machine (TPM) in der Arbeitsgruppe entwickelt. Es wurde gezeigt, dass die Verschlüsselung mit gängigen Verfahren nicht zu brechen ist.

Die Arbeit ist konzeptueller Natur. Der nächste Schritt ist die Implementierung des Protokolls in Software/Hardware. Abschlussarbeiter und Studienarbeiter sind herzlich willkommen!

Literatur:

• T. Kuhr: Analyse von RFID-Protokollen zur Implementierung eines Schlüsselaustauschverfahrens mittels PPM, Studienarbeit, TUHH, 2010.

Weiterführende Literatur (PPM):

• O. Reyes, I. Kopitzke, K.-H. Zimmermann: Permutation parity machines for neural synchronization. J. Physics A: Math. Theor., vol. 42, 195002, 2009.

• O. Reyes, K.-H. Zimmermann: Permutation parity machines for neural cryptography. Phys. Rev. E, vol. 81, 066117, 2010.

Simulating Swarm Behaviour

The emergent collective intelligence of groups of simple agents known as swarm intelligence is a new exiting way of achieving a form of artificial intelligence. This paper studies a formal model for swarm intelligence inspired by biological swarms found in nature. Software agents are used to model the individuals of a swarm. Each agent is controlled by a neural network that processes position data from the others in its visible zone given by a compound eye and in this way navigates in 3D space. An additional input parameter is used to represent the agent’s motivation to form a swarm. Simulations with different motivation parameters exhibit remarkable agent formations that can be considered as biologically plausable. Several ways to improve the model are discussed.

W. Kramper, R. Wanker, K.-H. Zimmermann: Analysis of Swarm Behavior Using Compound Eye and Neural Network Control. J. Sig. Proc. Systems, submitted.

Graphics Card Processing: Accelerating Profile-Profile Alignment

Alignment is the fundamental operation in molecular biology for comparing biomolecular sequences. The most widely used method for aligning groups of alignments is based on the alignment of the profiles corresponding to the groups. We show that profile-profile alignment can be significantly speeded up by general purpose computing on a modern commodity graphics card. In this way, the huge computational power of graphics cards can be exploited to develop high performance solutions for multiple sequence alignment.

Keywords Alignment · Progressive alignment · Graphics processor card · Basic linear algebra subprograms · Performance.

M.K. Hanif, K.-H. Zimmermann: Accelerating Profile-Profile Alignment Using Graphics Processor Units. J. Sig. Proc. Systems, submitted.

Reed-Muller Codes Revisited

Recently, we studied linear codes as ideals in the group algebra over an elementary abelian p-group. These codes can be described in terms of Groebner bases which in turn provide encoding and decoding procedures. In particular, we investigated generalizations of primitive Reed-Muller codes and constructed corresponding Groebner bases. We also showed that the class of codes studied contains an interesting family of linear codes. These codes have a designed Hamming distance and turn out to be superior to the primitive Reed-Muller codes in the non-binary case.

AMS Subject Classification: 13P10, 94B05

Keywords: Commutative polynomial rings, ideals, Groebner bases, Reed-Muller codes, decoding.

M. Saleemi, K.-H. Zimmermann: From Ideals in Polynomial Rings to Linear Codes using Groebner Bases. Int. J. Pure Appl. Math., to appear.

DNA Computing

During the last years, we have studied various DNA based models. These models generally encode information by DNA and manipulate information by enzymes. The emphasis has been on autonomous models (i.e., models that work without hand-crafting). The applications of autonomous DNA models lie in the analysis of  DNA in vitro and eventually in the logical control of cell behaviour in vivo.

Our main inventions have been an autonomous DNA model for finite-state machines, an automaton called computational genes able to logically control cell activities, the first autonomous solution of Adleman's first experiment, a bunch of new sticker-based algorithms, and a method that allows to implement sticker-based algorithms in silico onto dedicated hardware (FPGA).

 Literature:

• I. Martinez-Perez, W. Brandt, M. Wild, K.-H. Zimmermann: Bioinspired parallel algorithms for maximum clique problem on FPGA architectures. J. Sig. Proc. Syst., 1939-8115 (online), 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for finite state automata. Int. J. Bioinform. Res. App., vol. 5, no. 1, 81-96, 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Exploiting the features of finite state automata for biomolecular computing. J Recent Patents DNA & Gene Sequences, vol. 3, no. 2, 130-138, 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: DNA Computing Models. Springer, 300 pages, 2008.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Computational genes. Wikipedia, 2008.
• I. Martinez-Perez: Biomolecular Computing Models for Graph Problems and Finite State Automata. PhD thesis, mbv Berlin, 2007.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Computational genes: A tool for molecular diagnosis and therapy of aberrant mutational phenotype..BMC Bioinformatics, vol. 8, 365, 2007.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for finite state automata. Techn. Report, 06.1, TUHH, 2006
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Solving the maximum clique problem via DNA haiprin formation. Techn. Report, 06.3, TUHH, 2006.
• I. Martinez-Perez, Z. Ignatova, Z. Gong, K.-H. Zimmermann: Solving the Hamiltonian path problem via DNA hairpin formation. Int. J. Bioinform. Res. App., vol. 1, 389-398, 2006.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for stochastic finite state automata. Techn. Report, 06.2, TUHH, 2006.

A computational gene is an autonomous molecular automaton that is able to assemble an anti-drug or a wild-type gene if the mRNA of an aberrant gene has been detected. Computational genes have been successfully tested in vitro.

Patent:

• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Rechengen/Computer Gene/Gene de Calcul, DE/EN/US, 2007-09. 

A careful design of DNA strands is crucial for several biological applications such as microarray techniques, Polymerase Chain Reaction (PCR), and DNA computing. For this, the important criterion under laboratory conditions is the hybridisation energy of two DNA strands. During the last decade, a thermodynamic model was developed that allows for the calculation of the DNA/DNA hybridisation energy and recently also the cross-hybridisation energy of structural motifs.

We have developed a new algorithm for the secondary structure prediction of DNA/DNA cross-hybridisation complexes called HYBGRAPH. The method is based on Gibbs free energy minimisation and the paradigm of dynamic programming.

Literature:

• S. Torgasin, K.-H. Zimmermann: Algorithm for thermodynamically based prediction of DNA/DNA crosshybridisation. Int. J. Bioinform. Res. App., vol. 6, no. 1, 82-97, 2010.

 DNA computing is an integral part of our teaching activities (rotative seminar in the summer term).

Und wie hoch ist Ihre Erdös-Zahl?

Der Ungar Paul Erdös (1913-1996) war einer der bedeutendsten Mathematiker des zwanzigsten Jahrhunderts. Er galt unter Mathematikern schon zu Lebzeiten als eine Legende. Paul Erdös wuchs in Budapest als Sohn jüdischer Eltern auf. Mit vier Jahren konnte er Freunden der Familie im Kopf ausrechnen, wie alt sie gemessen in Sekunden waren. Paul wurde zuhause unterrichtet, da seine beiden Schwestern früh starben und seine Mutter Angst hatte ihn durch eine ansteckende Krankheit zu verlieren. Schon mit 17 Jahren besuchte er die Universität und nach nur vier Jahren erlangte er den Doktortitel in Mathematik. Da der Antisemitismus immer mehr zunahm, ging er im gleichen Jahr nach England.

Erdös' Arbeitsgebiete waren Kombinatorik und Zahlentheorie. Erdös gilt als Begründer der Diskreten Mathematik, die heute grundlegend für die Informatik ist. Erdös war ein ruheloser Geist, der neben USA, England sowie Niederlande auch Israel bereiste und dort von Universität zu Universität zog, um mit Wissenschaftlern zusammenzuarbeiten. Der polnische Mathematiker Stanislaw Ulam, ein Mitarbeiter des Manhattan Projektes, beschrieb Erdös einmal wie folgt:

He had been a true child prodigy, publishing his first results at the age of eighteen in number theory and in combinatorial analysis. Being Jewish he had to leave Hungary, and as it turned out, this saved his live. In 1941 he was twenty-seven years old, homesick, unhappy, and constantly worried about the fate of his mother who remained in Hungary. ... Erdös is somewhat below medium height, an extremely nervous and agitated person. ... His eyes indicated he was always thinking about mathematics, a process interrupted only by his rather pessimistic statements on world affairs, politics, or human affairs in general, which he viewed darkly. ... His peculiarities are so numerous it is impossible to describe them all. ... Now over sixty, he has more than seven hundred papers to his credit.

Erdös veröffentlichte circa 1.500 Artikel, so viele wie kein anderer Mathematiker. Daraus entstand scherzhaft die Erdös-Zahl. Erdös selbst hat die Erdös-Zahl 0, alle Koautoren, 509 an der Zahl, mit denen Erdös publizierte, haben Erdös-Zahl 1. Autoren, die mit Koautoren von Erdös, aber nicht mit Erdös selber veröffentlicht haben, besitzen Erdös-Zahl 2, usw. Wissenschaftler, die auf diese Weise keine Verbindung zu Erdös herstellen können, haben Erdös-Zahl unendlich. Die Erdös-Zahl der meisten Wissenschaftler ist entweder unendlich oder sehr klein. Der Mittelwert der ungefähr 268.000 Personen mit endlicher Erdös-Zahl liegt bei 4,65.

An der TUHH gibt es drei Wissenschaftler mit Erös-Zahl drei (Gollmann, Rump und Zimmermann) sowie ca. zehn Wissenschaftler mit Erdös-Zahl vier, darunter unser verehrter Uni-Präsident, Prof. Kreuzer. Kollege Mackens fällt nicht diesen Kreis - Angewandte Mathematiker haben oft höhere Erdös-Zahlen.

Die American Mathematical Society (AMS) pflegt eine Webseite, mit deren Hilfe sich Erdös-Zahlen berechnen lassen. Die Erdös-Zahl ist für den einzelnen Mathematiker nicht von Belang. Sie liefert jedoch im Rahmen wissenschaftlicher Publikationen ein Beispiel für ein Bekanntheitsnetzwerk. Derartige soziale Netzwerke gewinnen speziell im Internet immer stärker an Bedeutung (z.B. facebook). Im Bereich der Schauspielerei gibt es eine analog definierte Zahl, die Bacon-Zahl, die kürzeste Distanz zu Kevin Bacon (geb. 1958).

Wer mehr über Erdös erfahren möchte, dem sei der Dokumentarfilm N Is a Number: A Portrait of Paul Erdős von G.P. Csicsery (1993) empfohlen.

Simulation of Swarm Behaviour

The emergent collective intelligence of groups of simple agents known as swarm intelligence is a new exiting way of achieving a form of artificial intelligence. We are studying a formal model for swarm intelligence inspired by biological swarms found in nature. Software agents are used to model the individuals of a swarm. Each agent is controlled by a neural network that processes position data from the comrades in its visible zone given by a compound eye and in this way allows it to navigate in 3D space. An additional input parameter is used to represent the agent’s motivation to form a swarm. Simulations with different motiviation parameters exhibit remarkable agent formations that can be considered as biologically plausable. Several ways to improve the model are currently discussed.

Key Words: computational intelligence - swarm simulation - multi-agent system - neural network - compound eye.

Literature:

• W. Kramper: Simulation von Schwarmverhalten. PhD thesis, 124 p., mbv, Berlin, 2010.

Common work with Wolfgang Kramper and Ralf Wanker.

Bioinformatics Algorithms on Graphics Hardware

Alignment is one of the basic operations in molecular biology to compare sequences. The most widely used methods for multiple-sequence alignment include scalar-product based alignment of groups of sequences. 

We have shown that scalar-product based alignment algorithms can be significantly speeded up by general-purpose computing on a modern commonly available graphics card. This allows to develop high performance solutions for multiple-sequence alignment by utilizing the huge computational power of graphics cards.

Key Words  alignment - progressive alignment - graphics processor card - basic linear algebra subprograms - performance 

Literature

• C.S. Bassoy, M. Yang, S. Torgasin, K.-H. Zimmermann: Accelerating scalar-product based sequence alignment using graphics processor units. J. Sig. Proc. Syst., 1939-8115 (online), 2009.
• GPGPU.org

Groebner Bases for Linear Codes

Error-correcting codes are used to enable reliable delivery of digital data over unreliable communication channels. This typically involves to add extra bits to make the transmission of data more robust to disturbance present on the transmission channel. In particular, linear codes provide an extra structure that allows an efficient encoding of the data.

Recently, Fitzpatrick et al. have associated binomial ideals with binary linear codes. Groebner basis computations were used for decoding and to solve several problems related to graphs associated with the code.

More recently, we have emphasized that linear codes over prime fields can be described by binomial ideals each of which given as the sum of a toric ideal and a non-prime ideal. This description allows to study linear codes by methods from commutative algebra and algebraic geometry. The strength of this approach lies in the fact that the investigations can be made over any field and so particularly over an algebraically closed field of characteristic 0, which is the most comfortable situation in commutative algebra and algebraic geometry.

First, minimal generators of the binomial ideal of a code have been studied. The situation has turned out to be quite similar to the toric case. In the binary situation, the Graver bases, the universal Groebner bases, and the set of circuits of the binomial ideal are essentially equal.

Second, we have shown that the binomial ideal associated with a linear code has a very natural Groebner basis with respect to the lexicographic order requiring that any monomial containing one of the information symbols is larger than any monomial containing only parity check symbols. We have also illustrated that Groebner bases for linear codes provide a very compact representation of the encoding and decoding functions.

Third, we have studied the affine varieties of the binomial ideals associated with linear codes and minimal primary decompositions of these ideals.

Finally, we have described the binomial ideals of linear codes in terms of their syzygy modules and the corresponding finite free resolutions.

By the way, Groebner bases were first used in coding theory by Cooper providing a decoder for cyclic codes. Then the application of Groebner basis computations to the study of linear codes became an active field of study.

Originally, the method of Groebner bases was introduced by Buchberger for the algorithmic solution of some of the fundamental problems in commutative algebra. Today, Groebner bases provide a uniform approach to solving a wide range of problems expressed in terms of sets of multivariate polynomials such as the solvability and solving algebraic systems of equations, ideal and radial membership decision, effective computation in residue class rings modulo polynomial ideals, linear diophantine equations with polynomial coefficients, algebraic relations among polynomials, implicitization, and inverse polynomial mappings.

AMS Subject Classification: 13P10, 94B05

Key Words: commutative polynomial rings - binomial ideals - Groebner bases - linear codes - encoding and decoding.

Literature:

• M. Saleemi, K.-H. Zimmermann: Groebner bases for a class of ideals in commutative polynomial rings. Int. J. Pure Appl. Math., vol. 58, no. 1, 1-9, 2010.
• M. Saleemi, K.-H. Zimmermann: Linear codes as binomial ideals. Int. J. Pure Appl. Math., vol. 61, no. 2, 2010.
• M. Saleemi, K.-H. Zimmermann: Groebner bases for linear codes. Int. J. Pure Appl. Math., vol. 62, no. 4, 481-491, 2010.
• M. Saleemi, K.-H. Zimmermann: Syzygies and free resolutions of linear codes. Int. Electr. J. Pure Appl. Math., to appear
• M. Saleemi, K.-H. Zimmermann: Primary decompositions of linear codes. Int. Electr. J. Pure Appl. Math., submitted.

Permutation Parity Machines for Synchronization and Neural Cryptography

Synchronization of neural networks was studied in recent years as an alternative to cryptographic applications such as the realization of symmetric key exchange protocols. Our research provides a first view of the so-called permutation parity machine, an artificial neural network proposed as a binary variant of the well-known tree parity machine.

First, the dynamics of the synchronization process by mutual learning between permutation parity machines has been studied. By the way, the dynamics can be described by a first-order Markovian process. It has turned out that for neural synchronization, permutation parity machines form a viable alternative to tree parity machines.

Literature:

• O. Reyes, I. Kopitzke, K.-H. Zimmermann: Permutation parity machines for neural synchronization. J. Physics A: Math. Theor., vol. 42, 195002, 2009.

Second, the ability to synchronization between two permutation parity machines has been used to introduce a key-exchange protocol. This approach is quite similar to the case of tree parity machines. We have studied their performance against common attacks (simple, geometric, majority and genetic). It appears that the permutation parity machines (in opposition to tree parity machines) are rather immune against those attacks.

Literature:

• O. Reyes, K.-H. Zimmermann: Permutation parity machines for neural cryptography. Phys. Rev. E, vol. 81, 066117, 2010.

This paper was awared recently:

We are pleased to inform you that your article, "Permutation parity machines for neural cryptography," published in Physical Review E 81, 066117 (2010), has been selected for the July 1, 2010 issue of Virtual Journal of Biological Physics Research.  The Virtual Journal, which is published by the American Physical Society and the American Institute of Physics in cooperation with numerous other societies and publishers, is an edited compilation of links to articles from participating publishers, covering a focused area of frontier research.  You can access the Virtual Journal at http://www.vjbio.org -- thank you for your contribution. ...

Sincerely,
Robert H. Austin, Editor

Currently, the objective is to apply permutation parity machines to light-weight security, especially RFIDs. At this point, we want to set up several student projects.