Performance Prediction Project-Report 1999

Clique here for the Main page of the UMD/Rutgers/Syracuse performance prediction project.

In collaboration with David L. Rhodes (US Army CECOM/RDEC, Fort Monmouth) we considered the application of our performance prediction technology on the parallelization of Harmonic Balance Simulation equation, widely used in the analysis of nonlinear circuits. Nonlinear circuit simulations are computationally intensive and there have been many efforts for its parallelization. Most of the approaches have parallelized the related linear matrix operations(see the references in Irregular 99 conference paper[1] and have shown limited scalability properties. Our approach is novel, since it uses a task graph and an estimate of the execution and communication costs(performance prediction) to schedule the execution of the equations. We have experimented with different scheduling techniques of the task graph, dynamic, clustering and mapping using manually derived clusters and automatic clustering using the Pyrros+. We have observed significant performance improvements when using the clustering techniques and performance prediction of the weights over the dynamic approach. We have experimented with several circuits using the CRAY-T3E, IBM-SP2 and SGI Origin-2000. The results are reported in [1] and [2]. Our approach has achieved speedups of 32 on the CRAY-T3E which is the highest speedup ever reported for certain circuits such as microwave integrated circuit(MMIC). The results also demonstrate the importance of performance prediction for irregular task graph computation.

We also considered the application of performance prediction technology in improving the quality of the results as well the response time of searching the World Wide Web. Recently new search engine technology has appeared that utilizes the links between web pages to determine relations and popularity of the web pages. A search engine already exists in the public domain that utilizes this technology (www.google.com). The method used is related to the computation of a sparse large eigenvalue problem whose eigenvectors represent web communities ranked according to their values in the eigenvector. The major challenge is to compute the eigenvectors and eigenvalues of a very large graph very fast. Google's approach is to statically compute the ranking by finding the first eigenvector of the web graph. Considering the growth of the web such an approach tends to give high ranking to existing highly ranked pages and it will miss pages and communities of finer granularity. Our goal is to develop parallel methods that utilize performance prediction technology to achieve fast response time in real time searching. We have already built a preliminary prototype of a search engine that uses link based methods, to able to generate the data for our application. The quality of the results using link analysis is striking as compared to the standard text analysis engines such as AltaVista. These results have been reported in [3]. and can be found in DiscoWeb page along with our search Engine Design(Disco-Web).

In the forthcoming year we plan to look at the parallelization of irregular sparse matrix computation arising from Web Searches, using our performance prediction technology for task graphs(pyrros+). We would like to achieve response times in seconds instead of minutes or hours for large link graphs ranging from 10000 nodes up to a 1000000 of nodes. The Co-PI has participated with Rutgers University in a major donation by Sun Microsystems of two 64 node Enterprise 10000 parallel processor machines with 64 processor each, 64 Gbytes of main memory and 1.7 Terabytes of Disk memory. These machines are already operational and will be used in our research that is being supported by ARPA.

Publications:

[1] David L. Rhodes and Apostolos Gerasoulis: A Scheduling Approach to Parallel Harmonic Balance Simulation. To appear Concurrency International Journal of Foundations of Computer Science (IJFCS)

[2] David L. Rhodes and Apostolos Gerasoulis, Scalable Parallelization of Harmonic Balance Simulation. Lecture notes in Computer Science, Irregular 99, Springer.

[3] Davison, Gerasoulis et. al. DiscoWeb: Applying link Analysis to Web Search. 8th International World Wide Web Conference(WWW8), Poster Proceedings. P.148, 1999.


Last modified: 15 July 1999 by Apostolos Gerasoulis.