To start, the last handful of days have consisted of me making it to Seattle for bug days a meeting for Sage development, consisting mainly of bugs but also of other, development, like in my case M1RI. My mentor, Martin Albrecht will be coming to this event too.
I've worked on bitpacking, changing bitsliced groups into of rows of bits, have a output consisting of numerous shades of grey. Libpng is doing the low level work. I had ran into a problem, not properly setting up autotools to detect the library in the Makefile.am and this has now thankfully been fixed.
Done but in need of work, m*d_classic and m*d_strassen found here are in a state that has large portions of output, and has the amount of work reminiscent of the final state. What needs checking still is logic errors, which will be the main focus of next week.
A point of history that is noteworthy and relevant to this is this version of Strassen is not the original version but an optimization described in this paper called Strassen-Winograd. This is the mathematician, Shmuel Winograd who discovered the the asymptotically fast Coppersmith Winograd Algorithm which has not found widespread use currently due to the massive constant required for it to become efficient for matrix multiplication.
Tuesday, June 24, 2014
Monday, June 16, 2014
Week 4
Next:
Matrix multiplication proper is the next frontier. The code is already quite far along, with a 64*64 base case, strassen, and padding for multiplication. Peeling is another goal to work on, cutting off portions of the matrix for when the matrix does not form a square. This is best for when the input would otherwise waist a lot of time on unused values, from unused padding, and worst when the padding needed is minimal.
Issues:
After dealing with an issue of configuring autotools, libpng does produce output, albeit not colorful or conforming to inputs.
Matrix multiplication proper is the next frontier. The code is already quite far along, with a 64*64 base case, strassen, and padding for multiplication. Peeling is another goal to work on, cutting off portions of the matrix for when the matrix does not form a square. This is best for when the input would otherwise waist a lot of time on unused values, from unused padding, and worst when the padding needed is minimal.
Issues:
After dealing with an issue of configuring autotools, libpng does produce output, albeit not colorful or conforming to inputs.
Sunday, June 8, 2014
Input/Output and Permutation matrices
I/O is contained within the m1ri_io. At this point printing to ascii text is finished. Within the next week, input files for matrices will become a feature. Libpng, is optional, being less portable and is detected by autotools before functions relying upon it are used.
Permutation matrices are rather important and interesting. Using lapack style permutation matrices, they consist of an array where the array index and the respective value stored at index represent a row/column to be swapped. These will serve a major purpose later, being part of PLE decomposition, improving performance when working with sparse matrices.
Permutation matrices are rather important and interesting. Using lapack style permutation matrices, they consist of an array where the array index and the respective value stored at index represent a row/column to be swapped. These will serve a major purpose later, being part of PLE decomposition, improving performance when working with sparse matrices.
Sunday, June 1, 2014
Second week of Gsoc
Today marks the end of the first two weeks of coding, the first milestone of the GSOC. I’ve accomplished thorough tests for arithmetic, mod 3, mod 5, and mod 7, in matrices referred to as m3d_t , m5d_t, and m7d_t respectively.
I have a need to polish up a few functions, such as m*d_quarter, splitting a matrix into fourths not working on matrices less than 64 * 64. An optimal way to do Hadamard GF(5), and GF(7) is still unknown, though that's a low priority issue at the moment.
Coming soon, I'll start working libpng read and write, along with ascii input into M1RI. File input will make testing easier, and png files will add png files, along with being convenient, could make interesting art, depending on how numbers are represented. The smallest footprint involves shades of grey, though primary and secondary colors corresponding to values seems more interesting.
I have a need to polish up a few functions, such as m*d_quarter, splitting a matrix into fourths not working on matrices less than 64 * 64. An optimal way to do Hadamard GF(5), and GF(7) is still unknown, though that's a low priority issue at the moment.
Coming soon, I'll start working libpng read and write, along with ascii input into M1RI. File input will make testing easier, and png files will add png files, along with being convenient, could make interesting art, depending on how numbers are represented. The smallest footprint involves shades of grey, though primary and secondary colors corresponding to values seems more interesting.
Sunday, May 25, 2014
1st week of GSOC
This week I've got back into the swing of things, and have gotten tests worked on.
A large amount of the milestone needs to be finished, which at this point is mostly tests, which has more or less logic errors. The next week, I have laid out much better, with a clear vision of how how tests will work, relying on the communicative and associative property.
- For m3d, tests for addition and subtraction are complete, and hadamard needs to be tested.
- Addition and subtraction are tested by adding variable a to b, writing the result to c, then subtracting c from b and writing that result to variable d. Variable d is tested for equality to a.
- For m5d and m7d, tests are still a work in progress, hadamard needs to be finalized.
- A big issue had been remembering which representation was which and a confusion I had when communicating, over which bit was on which bitslice.
A large amount of the milestone needs to be finished, which at this point is mostly tests, which has more or less logic errors. The next week, I have laid out much better, with a clear vision of how how tests will work, relying on the communicative and associative property.
Thursday, May 22, 2014
GF(7) Elementwise multiplication needs further optimization.
I used a logic friday boolean logic optimization software to attempt to find an optimal set element wise multiplication (Hadamard). Unfortunately, this yielded disappointing results for the moment, not less than 70 bit operations. Possible ways to optimize include temporary bit slice during multiplication. This would mean that for the duration of the equation, the elements could be operated on as if they had four bits instead of three. Such as was first suggested here http://arxiv.org/abs/0901.1413 for GF(5), though a better representation has since been found for GF(5).
Tuesday, May 13, 2014
Submatrices, Addition, Subtraction, and Hadamard
The first major milestone of this project will be coding and setting up tests for the major building blocks of any feasible Matrix library. To start, wrappers for rand, free, and other essential library functions, will be worked on.Basic functions like m1ri_rand, and m1ri_free, have not appeared to any problems at this point, and seam to be working well.
Arithmetic in the form of element wise addition and multiplication (Hadamard Multiplication) is the first major area that is needing worked on. For GF(3), referred to as m3d, hadamard is implimented as element wise multiplication in that representation is trivial, taking 3 bit operations, half as many as is required for vector addition. GF(5), and GF(7) on the other hand, optimized in their representations for addition and traditional matrix multiplication, Boolean expression for element wise multiplication still found.
Tests with Autotools are an area that needs work, while simple benchmarks have been used, they've always been written on the fly and edited soon afterwards, and the current "tests" will succeed as long as the program doesn't have any syntax errors. To improve upon this, tests that check for logic errors with a pass fail on the aforementioned functions will be written in the following . Throughout this summer, testing for logic errors will be be a major theme of the project. This not only will make further work easier to build off of but will add to its legitimacy.
Arithmetic in the form of element wise addition and multiplication (Hadamard Multiplication) is the first major area that is needing worked on. For GF(3), referred to as m3d, hadamard is implimented as element wise multiplication in that representation is trivial, taking 3 bit operations, half as many as is required for vector addition. GF(5), and GF(7) on the other hand, optimized in their representations for addition and traditional matrix multiplication, Boolean expression for element wise multiplication still found.
Tests with Autotools are an area that needs work, while simple benchmarks have been used, they've always been written on the fly and edited soon afterwards, and the current "tests" will succeed as long as the program doesn't have any syntax errors. To improve upon this, tests that check for logic errors with a pass fail on the aforementioned functions will be written in the following . Throughout this summer, testing for logic errors will be be a major theme of the project. This not only will make further work easier to build off of but will add to its legitimacy.
Subscribe to:
Posts (Atom)