beepy0
commented
5 years ago Obsolete
One difference between the distributions and sizes being tested is the significant drop in Microarchitecture Usage for both the discrete normal and uniform 100k cases. Both indicate that the function Xi_EH3::element is being poorly utilized, although looking at the code for that function suggests the issue might be in subsequent calls made to other functions inside it.
The only thing that is being called other than the assignment of two variables is the function EH3, so any inherent problem should be part of that. The only difference between these two distributions and the other six is that both of them employ a strategy where values tend not to repeat often, especially for lower sample sizes. This effect could cause issues with Fast-AGMS but generally shouldn't impact AGMS due to the nature it generally processes new data. Expanding the Microarchitecture column reveals a pretty low CPI Rate, hinting that this is not a memory bound. VTune suggests to run a Microarchitecture Exploration Analysis in order to identify the issues. Another explanation for this deviation could simply be that this is a metric-related error coming from the fact that the VTune needed more data to display accurate results.
One assumption is that the distribution of the data would impact the throughput of the algorithm, as discussed previously. That didn't hold for AGMS, as the resulting time to complete the 100 million inputs run was withing margin of error for all three distributions, resulting in the same throughput up to the second decimal point. For FastAGMS though the benchmarks did yield somewhat of an increase in compute time going from zipfian to either normal or uniform, with uniform being the slowest, thus confirming our assumption for this test at least.
It is also no surprise that AGMS didn't get affected from the change of data frequency, since the vector being updated is the same for each input and is being fetched from cache in a sequential manner.
FastAGMS on the other hand hashes that input and calls for a somewhat random cell from each row of its update matrix, making it likely for cache misses to occur, or just stressing the system the more variance in the resulted hash there is. This can be also partially observed in the "other" section of the hotspots graph [REF], where the usage is increasing with the change of data in a similar fashion. That resulted in a throughput difference of close to 4% between zipfian and uniform data. Comparing the Fast-AGMS algorithm in terms of buckets size, there is no meaningful difference in terms of resulting throughput when it comes to the bucket size being a power of 2 or not. Note that the result could depend on the hardware, with varying architectures having different instruction bottlenecks.