Wednesday, July 4, 2012

High Performance Computing

                                    Bottom Up Tree Parallel Iterator Scheduling Scheme

Hello everyone,

I will be focusing on parallel computing,multithreading,multitasking,thread synchronization,and creating thread safe applications.
currently i have worked on creating a thread safe implementation for traversing a tree data structure in bottom up manner.I have used the existing JAVA api called iterator and extended its functionality to iterate over a tree in thread safe manner.

Multi-core computers are emerging as a new wave of technology and implementation of parallel running applications can better utilize the multi-core resources. It has been observed that traditional ways of programming and generating software have failed to fully utilize the enormous resources of today’s multi-core computers. The main idea of parallel computing is to divide large problems into smaller ones which are then solved concurrently. Computations carried out include various types and iterations are one of the most important types since traversing a collection is most common requirement for an application. Sequential Iterators cannot be used for parallel programming due to certain limitations and thus parallel iterator was developed that utilize the resources of CPU in an efficient manner. This paper presents various advancements of the parallel iterator, such as parallel traversal of complex collection i.e. a tree. Implementation includes bottom up traversal of unbalanced tree having common global queue for leaf nodes and bottom up traversal of unbalanced tree having separate queue for each thread i.e. work stealing approach. This paper presents the performance of different types of trees and an in-depth analysis of effects of workload has been done so as to determine the efficiency of Bottom Up Tree Parallel Iterator. The implementation has been done at the most appropriate level of inheritance making it easy to use.
If you are interested in reading the entire report email me at
To know more about parallel traversal of complex collection visit parallel Iterator.

My future work will be to parallelize searching process using paratask (PT)
which will enable me to create an efficient parallel algorithm to reduce the parallel overhead of recursive applications such as n queens problem,or XML/SVG files, or directory search(search for file/contents)

The main idea is that once a certain level of potential parallelism is created, then there is no need to keep creating asynchronous tasks,instead the tasks should be executed sequentially,however if too many tasks are executed sequentially then it might limit further parallelism later for its subtasks.
i am currently working on the above mentioned algorithm,stay tuned for further updates related to parallel computing,high performance computing and creating thread safe applications.

google-site-verification: google7d499775ef889383.html


  1. Seems to be interesting. In the last paragraph do you mean to say that tasks can be executed sequentially after some level of potential parallelism has been reached?

  2. Yup that correct..the main objective is to find out a point at which we need to stop creating threads and execute the tasks sequentially...
    If we keep on creating threads then there will be an overhead of thread creating,context switching and more utilization of stack space and CPU ends up taking more time to execute in parallel as compared to sequential which is counter productive.
    There is a fine line between creating threads and CPU utilization so once you detect the optimal point all the further tasks are executed in a sequential manner.