Shahid Hussain Bokhari - Research Interests

Research Interests

Bokhari's research interests include parallel and distributed computing, applied to computational biology and bioinformatics. He is, particularly, interested in parallel algorithms for DNA alignment and assembly.

One of Bokhari's most-cited research publication: "On the Mapping Problem" (1981) concerns the assignment of subtasks for distributed computation to processors in such a way that the subtasks that communicate with each other are, to the extent possible, assigned to the processors that are adjacent to each other within the communication network. His paper relates this problem to more abstract graph-theoretical problems, in particular, graph isomorphism. He also relates the problem to the representation of sparse linear systems as band matrices with low bandwidth, and to the quadratic assignment problem. This is the work for which Bokhari was cited in his IEEE Fellow award.

Several other highly-cited papers of Bokhari concern the partitioning and load balancing problems in distributed computing, the topic mentioned in his ACM Fellow award citation. As with the Mapping Problem, this concerns assignment of tasks to processors, but in a more general setting in which a processor may handle multiple tasks; the problem is to perform this assignment in such a way that heavily-communicating pairs of tasks are assigned to the same processor, while keeping the amount of work assigned to processors relatively even.

Bokhari's research with Marsha Berger (Berger and Bokhari 1987) concerns versions of the partitioning problem in which different tasks may have greatly differing workloads; he gives as an application the distributed solution of nonlinear partial differential equations. The technique introduced in this paper, recursive coordinate bisection, repeatedly divides the geometric problem domain along coordinate axes into two subdomains of equal workload until the number of subdomains formed equals the number of processors. However, as Simon writes, although this method is conceptually very simple it tends to produce long and thin or even disconnected subdomains. A later refinement of this technique, parametric binary dissection (Bokhari, Crockett, and Nicol 1993) combines shape information with load balancing in its partitioning decisions in an attempt to mitigate this problem. Another of Bokhari's papers (Bokhari 1988), his third most-highly cited, provides an algorithm that optimally solves the partitioning problem for several broad classes of distributed algorithm.