Contingency Table Analyses for Efficient Computing
Explore the importance of contingency table analyses in computing, especially with regards to the use of Chi-square tests and maximizing computational efficiency. Discover different strategies for optimizing the analysis process and overcoming challenges in handling large datasets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Contingency table analyses Milo Radi 12/0010 1/14
Introduction Statistics in computing Huge amounts of data Substantial number of operations required Potentiallyhighly parallel Maxeler can give a significant speed-up! 2/14
Contingency Table Analysis of two Distributions Measurement of association for two variables Each sample has two variables we observe We are given a contingency table for those two We are interested in their relation to each other Variable A Number of samples with a specific value of A and B Variable B 3/14
Contingency Table Analysis of two Distributions Let s use the Chi-square test We need all the row and column sums This part of the algorithm is good for Maxeler Scalar computations - CPU 4/14
Sum of elements Standard C implementation Initialize the sums with zeroes Use two nested for loops to sum Naive Maxeler implementation Straightforward copy of C code to Maxeler Scheduling fails! 5/14
Sum of elements We have an issue when summing rows Every tick we need the sum from the last tick But addition has a delay of 12 ticks 6/14
Sum of elements INPUT Input every tick MUX ADD Result after 12 ticks Compile error 7/14
Sum of elements Simple solution use Autoloop Offset Next input only when the last sum is computed Bad performance, pipeline is stalled frequently 8/14
Sum of elements Input every 12 ticks INPUT Counter = MUX offset - 1 ADD Result after 12 ticks -offset 9/14
Sum of elements Smarter solution input transposition We sum the colons using the original matrix We sum the rows using the transposed matrix 10/14
Sum of elements ORIGINAL INPUT TRANSPOSED INPUT MUX MUX ADD ADD COLON SUM ROW SUM -NUM_ROW -NUM_COL 11/14
CONCLUSION Idea of matrix transposition In this particular example no speed-up benefit What it reveals is suggestive but what it conceals is vital (same as a bikini) With more operations speed-up increases 12/14
References Trifunovic, N., Milutinovic, V., Salom, J., Kos,A., "Paradigm Shift in Big Data SuperComputing: DataFlow vs ControlFlow," Journal of Big Data, 2015, 2:4 (10 May 2015). Milutinovic, V., Salom, J., Trifunovic, N., Giorgi, R., "Guide to DataFlow SuperComputing," Springer, 2015. 13/14
Q&A 14/14
