The complete article describes how a simple search program for a 24MB database can be parallelized and distributed across several machines. Along the way, we discuss the C fork() and wait() library functions, shared memory, and Remote Procedure Calls (RPCs).
It is often assumed that parallelism and distributed programming always speed up sequential code. Fortunately, this rose-tinted view can be readily tested by timing the code. We do this for various search programs, and get some sobering results.
The test database holds membership details in ASCII, with one line per member, sorted by last name. The size of the database has meant that is is stored in four 6MB files called a2f.txt, g2l.txt, m2r.txt and s2z.txt.
A search query can be given any string, and must return the total number of database lines which contain that string. Also, up to 40 matching lines should be printed. Since the string may appear anywhere in a member's details, a simple linear search is used to scan the database.
The first approach uses fgrep running sequentially, and then in parallel. In response to slow times, we introduce srch.c which does the job quicker.
A drawback with fgrep and srch.c is that the search results cannot be easily manipulated. We solve that by recoding the search using fork(), wait() and shared memory in shpsearch.c.
Times for different database search methods:
------------------------------------------------
Time (in secs)
Types of Search Times for each Total
component file time
------------------------------------------------
1. fgrep and ';' 6, 7, 8, 6 27
2. fgrep and '&' 57, 58, 58, 57 58
3. srch.c and ';' 3, 3, 3, 3 12
4. srch.c and '&' 12, 13, 13, 14 14
5. shpsearch.c 14, 14, 14, 15 15
------------------------------------------------
Our final approach is to extend shpsearch.c to execute its component searches on different machines using RPCs. The three main files are:
rpcgen is used to generate the rest of the necessary code. For example, it generates match.h, the C version of the XDR types. The version of match.h given here had been edited so that only the ANSI C declaration are shown. This is simply to make the code easy to understand.
rpcgen can also be used to create 'skeleton' examples for the client main program (e.g. client-top.c) and the server function (e.g. server-func.c).
Six typical runs of the distributed search program (with four searches running on different machines):
------------------------------------------ Machine running the search. Time (in secs) ------------------------------------------ catsix 4 3 3 3 3 3 fivedots 1 1 2 1 1 0 fivedots 3 1 1 1 0 1 darkgrey 2 2 2 2 2 2 ------------------------------------------ Total search time 4 3 3 3 4 3 ------------------------------------------