5 ms·

Just reread my comment it's not vary clear: He has a lot of overhead related to random assignment in order to show a progress bar and he also seems to be using

Just reread my comment it's not vary clear: He has a lot of overhead related to random assignment in order to show a progress bar and he also seems to be using a insane number of threads. If you want to show steady progress as you do something to 1/2 of an MxN matrix join rows so x from top to x from bottom to get a constant amount of effort per Unit work + 1/2 unit effort if there is an odd number of rows. Basically, worst case is you have to wait for one core to process a full line when every other line is already finished. But, while you can cut the matrix into smaller chunks that tends to add overhead which is not worth it for large matrices split among a small number of cores. outer loop is x: 0 to N/2, worker does row x and row (N - x ). Now, in his case he wants a single number, that is the count of the number of comparisons over a threshold. In his example he works out that What about per-thread count arrays? but forget's that he can just keep a separate count per worker and then add it to the total when that worker finishes or split off a few workers add up the columns in those arrays. Which is far less single threaded code. PS: Cache coherency can be improved by splitting rows into 2d shapes or grouping rows into wider bands. The second option is a lot simpliar for a similar speedup as long as the bands are small enough not to blow your cache and you don't have to many worker threads. Basically, it's simple but not cache agnostic.

dalke 15y ago
I'm the author of that essay. I mentioned in passing in a couple of locations that the code I describe is only an approximation to the code which I am actually optimizing. The fingerprint objects are bit patterns of (in this case) 2048 bits, and the similarity between two fingerprints is defined as the number of bits in the intersection divided by the number of bits in the union. (This is the "Tanimoto" or "Jaccard" similarity.) Simple math says that if the one fingerprint has B bits, and the threshold is t, then fingerprints to search must have between Bt and B/t bits. What I do then to speed up the search is to precompute the popcounts for each fingerprint, sort them by popcount, and make an auxiliary index so I know where the start and end of each popcount count region is. As a consequence, this reduces the O(NN) term by a factor of two. With that in place, my sort algorithm is closer to: for (row=0; row<n; row++) { query_popcount = popcount(fingerprint[row]); start_popcount = num_bits*threshold; end_popcount = num_bits/threshold+1; for (target_popcount = start_popocount; target_popcount<end_popcount; target_popcount++) { for (col = start_of_popcount[target_popcount]; col<start_of_popcount[target_popcount+1]; col++) { num_bits_in_commmon = intersection_popcount(fingerprint[row], fingerprint[col]); if (num_bits_in_common / double(query_popcount + target_popcount - num_bits_in_common > threshold) { count++; } } } } This is less comprehensible than the version I posted in the essay, but still has the essential problem I wanted to resolve. With these optimizations in place, it's more complicated to determine the number of calculations which will be done in a row. For one, the popcount distribution is highly data dependent. I don't know that number until I'm in an inner loop, and so it isn't worthwhile to try and attempt to assign a "constant amount of effort per Unit work." In the usual case of high thresholds, and if the fingerprint popcount distribution is broad, then I am mostly working along the near-diagonal of the matrix, which improves my cache coherency. However, if I have enough fingerprints then this simple linear scan will blow the cache, and the above needs to be replaced by some cache oblivious search pattern. If that's what you meant by "2d shapes" in your comment then perhaps you missed my mention of Morton Z-ordering? My goal, however, was to explain the thinking needed to minimize lock contention and the difficulties in developing a parallel algorithm, so I used a simplified version of what I actually did to get that point across. Your comments deal with other aspects of the algorithm, and don't contribute to the point. BTW, what do you mean by "insane number of threads"? The target is a 8 core machine, and my timings numbers show a scaleup of about 6x for that case. I'm used to working on parallel molecular dynamics codes which use 10-100 processors, so this seems rather small. Also, "he can just keep a separate count per worker and then add it to the total when that worker finishes" isn't correct, or rather, I can't see how to apply it to the symmetric form. The code I came up with has one single-threaded code, of O(N) time, and after the final barricade. I don't see how any other solution has less contention.
- scott_s 15y ago
  He's probably referencing this line: This is likely the cost of starting N=110885 different worker threads in Python. That's not actually accurate, but it's just a terminology problem. When you say "thread," what people like me think of is the actual operating system kernel thread. In your Python code, you only have 4 of them at any given time. (I know this from "max_workers=4".) What I think you mean by it is "indivisible work unit I'm supplying to my threading library," and I think you have 110885 of them.
  - dalke 15y ago
    Ah, thanks! I've fixed the problematic text.
- Retric 15y ago
  That's useful and info that the article did not have, but so I know where the start and end of each popcount count region is At which point you know the width of each row and can keep a running total for the progress bar as the row finishes. Again this is only important because randomly assigning threads significantly degrades performance. "The code I came up with has one single-threaded code, of O(N) time, and after the final barricade. I don't see how any other solution has less contention." //I will assume your O(N) code is basically N=numer of fingerprints, B = number of OS level threads. for (x=0, x < N, x++) {for (y=0, y < B, y++) { total[x]+= arraylist[y][x];}} It's easy to turn this into multi threaded code because each x can be calculated independently. The other optimization where worker threads that run out of job add up their totals to each other which is then added to the end result is the other multi threaded speedup. With it's own set of tradeoffs. PS: You can always optimize more, but it's midnight and I am not staying up to think about this any more. Anyway, thanks for sharing.

dalke 15y ago

I'm the author of that essay. I mentioned in passing in a couple of locations that the code I describe is only an approximation to the code which I am actually optimizing. The fingerprint objects are bit patterns of (in this case) 2048 bits, and the similarity between two fingerprints is defined as the number of bits in the intersection divided by the number of bits in the union. (This is the "Tanimoto" or "Jaccard" similarity.) Simple math says that if the one fingerprint has B bits, and the threshold is t, then fingerprints to search must have between Bt and B/t bits. What I do then to speed up the search is to precompute the popcounts for each fingerprint, sort them by popcount, and make an auxiliary index so I know where the start and end of each popcount count region is. As a consequence, this reduces the O(NN) term by a factor of two. With that in place, my sort algorithm is closer to: for (row=0; row<n; row++) { query_popcount = popcount(fingerprint[row]); start_popcount = num_bits*threshold; end_popcount = num_bits/threshold+1; for (target_popcount = start_popocount; target_popcount<end_popcount; target_popcount++) { for (col = start_of_popcount[target_popcount]; col<start_of_popcount[target_popcount+1]; col++) { num_bits_in_commmon = intersection_popcount(fingerprint[row], fingerprint[col]); if (num_bits_in_common / double(query_popcount + target_popcount - num_bits_in_common > threshold) { count++; } } } } This is less comprehensible than the version I posted in the essay, but still has the essential problem I wanted to resolve. With these optimizations in place, it's more complicated to determine the number of calculations which will be done in a row. For one, the popcount distribution is highly data dependent. I don't know that number until I'm in an inner loop, and so it isn't worthwhile to try and attempt to assign a "constant amount of effort per Unit work." In the usual case of high thresholds, and if the fingerprint popcount distribution is broad, then I am mostly working along the near-diagonal of the matrix, which improves my cache coherency. However, if I have enough fingerprints then this simple linear scan will blow the cache, and the above needs to be replaced by some cache oblivious search pattern. If that's what you meant by "2d shapes" in your comment then perhaps you missed my mention of Morton Z-ordering? My goal, however, was to explain the thinking needed to minimize lock contention and the difficulties in developing a parallel algorithm, so I used a simplified version of what I actually did to get that point across. Your comments deal with other aspects of the algorithm, and don't contribute to the point. BTW, what do you mean by "insane number of threads"? The target is a 8 core machine, and my timings numbers show a scaleup of about 6x for that case. I'm used to working on parallel molecular dynamics codes which use 10-100 processors, so this seems rather small. Also, "he can just keep a separate count per worker and then add it to the total when that worker finishes" isn't correct, or rather, I can't see how to apply it to the symmetric form. The code I came up with has one single-threaded code, of O(N) time, and after the final barricade. I don't see how any other solution has less contention.

scott_s 15y ago
He's probably referencing this line: This is likely the cost of starting N=110885 different worker threads in Python. That's not actually accurate, but it's just a terminology problem. When you say "thread," what people like me think of is the actual operating system kernel thread. In your Python code, you only have 4 of them at any given time. (I know this from "max_workers=4".) What I think you mean by it is "indivisible work unit I'm supplying to my threading library," and I think you have 110885 of them.
- dalke 15y ago
  Ah, thanks! I've fixed the problematic text.
Retric 15y ago
That's useful and info that the article did not have, but so I know where the start and end of each popcount count region is At which point you know the width of each row and can keep a running total for the progress bar as the row finishes. Again this is only important because randomly assigning threads significantly degrades performance. "The code I came up with has one single-threaded code, of O(N) time, and after the final barricade. I don't see how any other solution has less contention." //I will assume your O(N) code is basically N=numer of fingerprints, B = number of OS level threads. for (x=0, x < N, x++) {for (y=0, y < B, y++) { total[x]+= arraylist[y][x];}} It's easy to turn this into multi threaded code because each x can be calculated independently. The other optimization where worker threads that run out of job add up their totals to each other which is then added to the end result is the other multi threaded speedup. With it's own set of tradeoffs. PS: You can always optimize more, but it's midnight and I am not staying up to think about this any more. Anyway, thanks for sharing.