MULTICORE PARALLELIZATION OF AN INDEXER IN QUESTION ANSWERING SYSTEM AND PAGE RANK ALGORITHM

Abstract

Explosive growth of information over internet and increasing number of users of WWW are throwing major challenges to the web applications. In order to deal with this growth, web applications are utilizing increased processing hardware. The need of hardware is currently served by connecting thousands of computers in cluster. But faster and less complex alternatives to this system can be found as a multi-core processor. A recent breakthrough with introduction of the STI Cell Processor and GPU multiprocessors has provided a new alternative for the researchers to port computationally intensive applications on them. A question answering system is an information retrieval application which allows users to directly obtain appropriate answers to a question. Over the time, in order to provide more accurate and relevant answer, processing stages in question answering systems have increased many times. Tasks like indexing a huge document set and retrieving answer to the user query are highly computational intensive and consume significant processing time. As a part of this dissertation we identify major issues involved in porting a general question answering framework on Cell processor and their possible solutions. The work is evaluated by porting the indexing algorithm of a biomedical question answering system, INDOC (Internet Doctor) on Cell processor. In order to provide most relevant results to a search query, search engine Google implemented a ranking technique (called PageRank algorithm) for assigning ranks to all web pages. Page rank of a particular web page is determined by page rank of all those web pages which are pointing to this web page. 'Besides this, PageRank algorithm works upon a large number of web pages. Thus the PageRank calculation is computational intensive. In this dissertation we identify major issues involved in porting PageRank algorithm on Cell BE Processor and CUDA, and their possible solutions. The work is evaluated by taking three input graphs of different size ranging from 0.35 million nodes to 1.3 million and comparing results with previous implementation of PageRank on Cell BE.