Parallel Linear Programming in Fixed Dimensions Almost Surely in Constant Time

• Solved simply with a ray shooting algorithm
• Pick a random point, and draw a line perpendicular to the x-axis
• Find the convex hull line intersecting this line

• We may represent the ray shooting algorithm as a linear program
• Linear program made up of two parts:
  • Objective Funciton: Search for a line with the lowest intercept
  • Constraints: Line must be above (or on) all point

• Naturally this is a 2 dimensional linear program
• Sequential Randomized Quickhull: algorithm
• Parallel Randomized Quickhull:
• Interested in implementing this on GPUs
• This is not realistic!

• Infeasible: At most constraints describe infeasible
• Feasible: Optimal solution within constraints

• We want our linear program to only have a single solution
  • If the random chosen point is on the convex hull, there are 2 (or )
  • Otherwise, there is only a 1
• We will assume there is only a single optimal solution
  • Though the actual algorithm accounts for this

• Let
• 2 arrays: and
• is a set of random constraints we sample
• is the sample space of constraints
  • First constraints are from linear program
  • Other constraints are dummies

• Sample constraints from into
• Solve constraints of using brute force
  • Take every pair of constraints in and find the optimal
  • Find the minimum which is within all

• Take the solution of and check across all constraints
• For any constraint not satisfied, replicate it times in
  • If there is not enough space, wrap around the array
  • The idea is the defining set we need get replicated exponentially

Theorem 1

This algorithm must finish in less than iterations.

• constraints make up the defining set
• All solutions not involving the defining set will always violate these conditions
• Constraints will be replicated times
• which is a contradiction
• Naturally, time complexity is

• Sequential algorithm is extremely simple
• There is a lot of room for parallelization
  • Finding the optimal of is all independent
  • Finding which constraints are violated is also extremely parallel

• Three major bottle necks
  • Checking if a solution fits all of the constraints
  • Finding the minimum of possible solutions for
  • Replicating the violated constraints (requires compacting the output)

• PRAM Model is the analog for RAM in parallel
  • Each processor has a private register
  • All processors access the same global memory
  • Each processor runs the same code in lockstep
• Memory conflict protocols
  • CRCW, CREW, EREW
  • CRCW is the most powerful model
  • Also happens to be the only protocol which can parallelize in constant time

• CRCW typically resolves conflicts through arbitrary winner
• CRCW style is mainly only implemented on FPGA architectures
• GPUs are not CRCW, closer to CREW

• Compaction and Minimum Problem are at least as difficult as logical OR
  • A lower bound on logical OR establishes a lower bound on these two
• Cook Et al. (1986)
  • Establishes on logical OR of bits on CREW

• CREW is a bit strict for the GPU
  • GPUs are closer to CRQW
  • Queued Write (QW) = Concurrent writes are queued
• Kutylowski and Lorys (1996)
  • Suppose a processor may dectect how long they have been trying to write
  • If they have waited for too long, then the processor should be able to cancel
  • Logical OR may be calculated in time

• Nvidia's Cuda does not appear to have this functionality
  • AMD GPU's also do not appear to have this as an instruction
• Currently stuck with an at best solution to the problem

• Prove this is a Beyond Worst Case algorithm
  • For any input, this algorithm will perform as good as the best algorithm for this input