I want to implement a parallel clustering algorithm "out-of-core" in CUDA. My CPU has 12GB of RAM and GPU has 4GB of it. What I want is that the entire dataset should be on the disk, and I can pick blocks of data from it, put the blocks on CPU memory, pass them to the GPU, process it there and store the result back on disk. The step complexity of the original (in-memory) algorithm is O(logN), N-> no. of data points. For the external memory algorithm, suppose M points can fit in the memory at once, then according to me, the running should be


(N/M) -> equals the number of such sets of points that will have to be put in memory and during each pass, logM time to process it.

How does this running time relate to the I/O time between disk and memory, i.e., have I already considered the I/O time by using (N/M) or am I leaving something out? Is this analysis correct, or do I need to know more about Input/Output to implement an algorithm using external memory?

1 Answer 1


The I/O time cost is going to be some number based on N, since you will ultimately read N objects from disk. So it might be included in your complexity estimate, assuming your method of "picking blocks" is constant time.

Remember, that just tells you the general order of complexity of the algorithm, and the factors that play the biggest role in that complexity for large values of N.

  • Thanks for the answer. Also, could you please explain how do I know if my method of "picking blocks" is of constant time?
    – pymd
    Apr 21, 2014 at 18:34
  • In your algorithm description you say that you will pick blocks of data to process. If this is just "grab m objects from disk", that's constant time. If the process of picking blocks involves a sort or search operation, it will increase the complexity of the overall algorithm.
    – jhauris
    Apr 21, 2014 at 18:38
  • I have a file containing the entire dataset. How I intend to pick the blocks is by assigning to each data point, a block number (in a pre-processing step) and then during picking the block, I'll simply 'seek' to the desired position and pick up the set of points. Will this 'seeking' work as a search? (I believe this should be contant time as I already know what position in memory to look for).
    – pymd
    Apr 22, 2014 at 4:26
  • It sounds like you are correct.
    – jhauris
    Apr 23, 2014 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.