4 ms·
> These offsets are obtained iteratively, stepping through the entire file buffer by the desired split size (= total file size / desired number of parts), and
by kevincox 3y ago
> These offsets are obtained iteratively, stepping through the entire file buffer by the desired split size (= total file size / desired number of parts), and marking the position of a new line character:
In many cases it is better to just pass the raw byte offsets to the workers, then they can skip to the first newline and progress until the next newline after their "end offset". This way the launcher doesn't need to access the input data at all.
This can be ineffective when boundaries are not self-describing or when the minimum processable chunk is near the expected batch size (as you will have significant swings in batch size) but I think would work quite well for this case.
- tspeterkim 3y agoBy "launcher", do you mean the CUDA kernel? How can it avoid accessing the input data since it needs access to the characters based on the offsets? I also already pass these offsets to the threads as `Part* parts`. I also probably didn't understand your suggestion and am drawing a blank here. So pls feel free to elaborate and correct me.
- tromp 3y agoHe's proposing to skip the whole computation of the parts[] array and within the kernel, replace for (int i = 0; i < parts[bx].length; i++) { // bx is the global thread index char c = buffer[parts[bx].offset-buffer_offset + i]; by something like long long split_size = size / num_parts; long long offset = bx * split_size; while (buffer[offset++] != '\n') ; for (int i = 0; buffer[offset+i] != '\n'; i++) { char c = buffer[offset + i]; (ignoring how to deal with buffer_offset for now).
- tspeterkim 3y agofor (int i = 0; buffer[offset+i] != '\n'; i++) { This would only process the current line, though. Here, each thread processes ~split_size bytes (multiple lines). Even if were to read multiple lines, how would a thread know when to stop? (at which offset?) And when it does, it should communicate where it stopped with the other threads to prevent re-reading the buffer. My brain's hurting now.
- tromp 3y agoIt can compute both the starting offset for itself and next_offset for (bx+1)...
- kevincox 3y agoYeah, this is a bug in their quick example code. Basically think that you simply give each thread a start and stop offset with simple byte division. Then each thread handles the first line that starts after the start offset up to but excluding the first line that starts after its end offset. So there will be a small amount of "overread" at the boundaries but this is probably negligible. let chunk_size = buf.length / threads; let start_byte = chunk_size * bx; let end_byte = start_byte + chunk_size; let i = start_byte; while (buffer[i++] != '\n') {} // Skip until the first new row. while (i < end_byte) { let row_start = i; let row_end = i; while (buffer[row_end++] != '\n') {} process_row(buffer, row_start, row_end); i = row_end + 1; } Basically you first roughly split the data with simple byte division. Then each thread aligns itself to the underling data chunks. This alignment can be done in parallel across all threads rather than being part of a serial step that examines every byte before the parallel work starts. You need to take care that the alignment each thread does doesn't skip or duplicate any rows, but for simple data formats like this I don't think that should be a major difficulty.
- tspeterkim 3y agoI tried this out today. While it works (no longer a pre-split step required), it makes the CUDA kernel run ridiculously slow. I believe it's because of the while loop: while (i < end_byte) { Comparing it to my original solution, 50X divergent branches are introduced! (ncu profiling) The only difference between the two is that the for loop could deterministically iterate, yet this while loop iterates for an unknown amount (at kernel launch time). I admit, I don't perfectly understand the reason. But this is the most likely culprit.