Abstract:

The objective of this project is to create a GPU - based, parallel reader of posting lists for Yioop. Yioop is an open source search engine designed and developed in PHP by Dr. Chris Pollett. We will be using OpenCL to code for the GPU. We will then do experiments comparing performance of our GPU posting list handler with the existing mechanism in Yioop. Search engines use an inverted index to look up for a term in all the documents containing that term. This list of documents is called a posting list. Posting lists are typically stored in a compressed binary format. OpenCL (Open Computing Language) provides a platform for parallel and efficient programming. GPUs have hundreds or thousands of processing units rather than one to eight for a typical CPU. OpenCL provides an effective way to program GPUs and to send and receive data from the CPU in a system and a GPU. Many posting list operations can be done in parallel. So implementing posting lists algorithm using OpenCL will likely improve the performance of search engine.

CS297 Results

• Understood different algorithms for index compressions and wrote a C-Program to implement Huffman encoder/decoder.
• Wrote a C-Program to encode/decode posting lists using Simple-9 compression algorithm.
• Installed the necessary C++ bindings for Microsoft Visual studio and wrote a OpenCL program to compute the squares of each element of an array.
• Installed PHP extensions for windows and wrote a simple PHP extensions for the hello world program.

Proposed Schedule

Key Deliverables:

• Software
  • Write a C-program to encode/decode posting lists using Modified-9 compression algorithm (existing Yioop's algorithm)
  • Convert above C-program into an OpenCL program
  • Write PHP Extensions to the above OpenCL program
  • Conduct performance comparison tests with the GPU posting handler and the exisiting Yioop system
• Report
  • CS298 Report
  • Project Code and Test results Documentation

Innovations and Challenges

• Working with novel index compression schemes
• Writing PHP extensions to the OpenCL
• Conducting performance testing to compare relative performance improvements may need dedicated hardware

References:

1. Stefan, B., Clarke , C., Cormack, G. (2010). Information retrieval - Implementing and Evaluating Search Engines . Cambridge, Massachusetts: MIT Press.

2. Benedict , G., Howes, L., Kaeli, D., Mistry, P., Schaa, D. (2011). Heterogeneous Computing with OpenCL. Morgan Kaufmann.

3. Golemon, Sara. Extending and Embedding PHP. Indianapolis, Ind.: Sams, 2006. Print.