2023年11月25日

Java代写 | COM6102 Project: An indexing web browser

这是一个并行算法代写作业案例分享

1 Overview

You can find the template files by this invitation link

https://classroom.github.com/a/hnj4vqr3

There are five files:

ˆ get time.h. This file includes functions for time testing. You don’t need to modify the file.

ˆ parse command line.h. This file includes functions to parse command line arguments. You don’t need
to modify the file.

ˆ qsort.cpp. This file is an example testing file for you. The actual testing code will be very similar,
but differs in how to generate input data. As you will see, the only function you need to implement
is the quicksort function. When you test your own code, you can modify any files as you need, but
please don’t leave anything useful in this cpp file.

ˆ qsort.h. You need to implement your quicksort function in this file. Of course you can add auxiliary
functions or variables, but please make sure to put all your code in this file.

ˆ makefile. This is also an example makefile to help you test your code. It is basically the same as
what we will use in final test. You can edit the file as you like. Also, do not put anything useful in
this file since that’s not used in the final test.

In this project, you need to submit:

ˆ A mid-report on Wed, 02/02. In the mid report, you need to report your current progress. The re
quirement of your mid report is to at least have a highly-optimized version of the partition algorithm.

You need to present how you implemented it and some testing data.

ˆ A final report on Fri 02/18. In the final report, you need to report how you implemented the entire
algorithm, what test data you designed and some testing result.

ˆ Your implementation of function quicksort in qsort.h (just commit and push your changes to github).

2 Brief Guideline

Here’s a brief guideline.

1. First, note that you need to implement a scan algorithm. For the best performance, you probably
want to avoid allocating memory during the algorithm. That is to say, if you need extra space, allocate
the memory in advance. This is because allocating memory in parallel can be expensive.

2. Then, based on your scan algorithm, implement a filter algorithm and then a partition algorithm.

3. For all of them, don’t forget to consider granularity control.

4. Then, you can implement your quicksort algorithm.

5. Next you need to test the correctness of your algorithm: you can use STL sorting algorithm compare
your output with STL.

6. Finally, you need to test the performance of your code. Try to design different test cases and test their
performance. If they show different performance, try to think about the reason behind that.

3 Possible Optimizations

Here are some optimizations and hints you can consider in your implementation. Of course, you can use
more.

1. Coarsening. Use the similar idea as shown in Homework 0 and 1. Try to find the best threshold to
determine a sequential or a parallel run.

2. You can call STL sorting algorithm or other existing sorting algorithms to work on the base cases.
Since STL is highly-optimized, it’s likely to give better performance than your sequential version.

3. Try to avoid using std::vector, especially avoid resizing it in parallel. This is because resizing involves
allocating and deallocating memory, which is also slow in parallel.

4. Try to design a hash function to generate random numbers instead of rand(). This is because this
function is not designed for running in parallel.

5. Choosing an arbitrary key as the pivot gives good theoretical bound using randomization, but in
practice we can even do more to avoid bad luck. For example, you can pick up t random elements in
the original array, find the median of them, and use the median as the pivot. This helps to split your
input in a more balanced way. t is usually selected as a small constant.

6. Of course you can think of more interesting optimizations!

4 Design Your tests

To test the performance, you will need to design some test cases with different patterns. This is to make
sure your algorithm performs well in different inputs, and to understand the good and bad cases for your
algorithm. In our final test, we will have five test cases, each of size 108. In all test cases, the input keys are
64-bit integers. For each test, we will use the average of the five runs as your final running time (running 6
rounds, and report the average of the last five rounds). The actual testing data will not be given (you need
to design your own input to test and debug), but the data pattern will be shown below.