Settings

Now showing1 - 3 of 3
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units
    (Springer, 2022-02-09)
    Hanif, Muhammad Kashif
    ;
    Zimmermann, Karl-Heinz
    ;
    Anees, Asad
    Bipartite graphs are used to model and represent many real-world problems in biological and physical sciences. Finding shortest paths in bipartite graphs is an important task and has numerous applications. Different dynamic programming based solutions to find the shortest paths exists which differ on complexity and structure of graph. The computational complexity of these algorithms is a major concern. This work formulates the parallel versions of Floyd-Warshall and Torgasin-Zimmermann algorithms to compute the shortest paths in bipartite graphs efficiently. These algorithms are mapped to graphics processing unit using tropical matrix product. The performance for different realizations and parameters are compared for Floyd-Warshall and Torgasin-Zimmermann algorithms. Parallel implementation of Torgasin-Zimmermann algorithm attained a speed-up factor of almost 274 when compared with serial Floyd-Warshall algorithm for random-generated undirected graphs.
    Publicationtype: Journal Article
      27
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Accelerating Viterbi algorithm on graphics processing units
    (Springer, 2017-05-19)
    Hanif, Muhammad Kashif
    ;
    Zimmermann, Karl-Heinz
    Viterbi algorithm is used in different scientific applications including biological sequence alignment, speech recognition, and probabilistic inference. However, high computational complexity of the Viterbi algorithm is a major concern. Accelerating the Viterbi algorithm is important, especially when the number of states or the length of the sequences increase significantly. In this paper, a parallel solution to improve the performance of Viterbi algorithm is presented. This is achieved by formulating a matrix product based algorithm. This algorithm has been mapped to a NVIDIA graphics processing unit. The performance for different parameters and realizations are compared. The results depicts matrix product is not a viable option for small number of states. However, matrix product solution using shared memory for large number of states gains good performance when compared with the serial version.
    Publicationtype: Journal Article
      117
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: with files ,
    Graphics card processing : accelerating profile-profile alignment
    (De Gruyter, 2012)
    Hanif, Muhammad Kashif
    ;
    Zimmermann, Karl-Heinz
    © 2012 Versita Warsaw. 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. Wavefront and matrix-matrix product approaches for implementing profile-profile alignment onto graphics processor are analyzed. The average speed-up obtained is one order of magnitude even when overheads are considered. Thus the computational power of graphics cards can be exploited to develop improved solutions for multiple sequence alignment.
    Publicationtype: Journal Article
    Scopus© Citations 1  301  293