Logn-LIS

Prerequisites

• g++ >= 7 with support for Cilk Plus and C++17 (It is tested with g++ 7.5.0)

Usage

We implemented all algorithms in C++ using ParlayLib and PbbsLib for fork-join parallelism and some parallel primitives.

1. Clone the project and its dependencies

   git clone --recurse-submodules git@github.com:ucrparlay/Parallel-LIS.git
   cd Parallel-LIS/
   

2. Compile the code:

   make
   

3. Run the project

   ./weighted_lis [-i input_file] [-a array_size] [-u array_limit] [-l lis_length] [-e weight_limit] [-r test_round] [-g generated_input] [-p data_pattern] [-w] [-s]
   

   Options:

   • -i input file path
   • -a size of input array
   • -u the upper limit of array values, if autogenerated
   • -l the length of LIS, if autogenerated
   • -e the upper limit of weight values, if autogenerated
   • -r numebr of test round
   • -g the filename of the autogenerated input data
   • -w weighted LIS algorithm
   • -s sequential LIS algorithm
   • -p data pattern: line, segment or random

For example, if you want to run the weighted parallel LIS algorithm on a LIS sequence INPUT_NAME of size 10000. Autogeneration of weight values is needed and the upper bound of these values should be 20, you can run:

./weighted_lis -i INPUT_NAME -a 10000 -e 20 -w