Project Partner Wanted
gennari
I am still looking for a project partner for CS267. I would like to
parallelize my pattern matching software. I have included the details below.
Reply if you're interested in working with me. Thanks.
Frank
> I would like to implement a parallel version of my pattern
matching
> program for the final CS267 class project. In fact, one of the main
reasons
> I'm taking CS267 is to learn how to parallelize the pattern matcher so
that
> it can run on large inputs without taking excessive time. The software is
in
> the CAD/lithography areas. It reads a hierarchical integrated circuit
> layout, a list of bitmap patterns to search for, and some user parameters.
> It then effectively scans the patterns over the geometry in the layout,
> searching for the locations with the best match, which are then drawn on
the
> display and output to a file. Typical runtimes are about half an hour per
> design layer per pattern for large layouts on modern PCs, though some
> special options can make the time even longer. I would like to write a
> parallel version to make the pattern matching nearly interactive, for
> example for use in a design rule checker. Pattern matching can also be
used
> similarly to OPC (see my HW0). I am looking for another student to work on
> this project with. You can find more info at:
>
> http://www.eecs.berkeley.edu/IPRO/Summary/02abstracts/gennari.1.html
>
> The webpage is an old research abstract - the new webpage is down. I
can
> also send you some papers on the research project if you want.
> I would like to spatially subdivide the layout in both the X and Y
> directions and process the partitions in parallel. I already partition the
> layout to conserve memory, but parallelization of the partitions is not
> easy. The partitioning is somewhat complex since the partitions must
overlap
> and load balancing may be difficult. Also, the current algorithm uses an
> approximation method that is based on previously computed statistics
> (actually computed error predictions), and these values would have to be
> communicated between the processes at various intervals in order to
> effictively use the approximation algorithm. I'm not sure if there is a
way
> to load the hierarchical layout database in parallel or efficiently
> distribute the storage - this would be difficult.
>
> The computation will likely still dominate over the communication, so I
> think it would work well on a distributed memory system. I think MPI would
> work for this. The program is in C++, but most of the inner loops where
> performance is critical are really in C. There are several modules in the
> software system totaling about 60,000 lines, but the part I would be
> optimizing is more like 10,000 lines or so. Most of the code blocks would
be
> untouched since the new parallel code will go into the spatial subdivision
> algorithm and the outer loops.