Created
July 7, 2020 09:01
-
-
Save globalpolicy/bb74dbbe7500b9d51da00b4797c7064d to your computer and use it in GitHub Desktop.
Large matrix multiplication with GPU.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <html> | |
| <head> | |
| <script src="https://cdn.jsdelivr.net/npm/gpu.js@latest/dist/gpu-browser.min.js"></script> | |
| </head> | |
| <body> | |
| <script src="main.js"></script> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 'use strict'; | |
| var gpu; //GPU instance variable for GPU.js | |
| let start_time, output, stop_time; | |
| let mat1 = []; | |
| let mat2 = []; | |
| let n = 2000; | |
| //initialize data. matrices are assumed to be square and the same dimensions | |
| let row = []; | |
| for (let i = 0; i < n; i++) { | |
| row = []; | |
| for (let j = 0; j < n; j++) { | |
| row.push(Math.floor(Math.random() * 10)); | |
| } | |
| mat1.push(row); | |
| } | |
| for (let i = 0; i < n; i++) { | |
| row = []; | |
| for (let j = 0; j < n; j++) { | |
| row.push(Math.floor(Math.random() * 10)); | |
| } | |
| mat2.push(row); | |
| } | |
| //gpu computation | |
| gpu = new GPU(); //instantiate gpu. used by gpuCompute() | |
| //2 blocks of size 1000 | |
| start_time = performance.now(); | |
| output = gpuCompute(mat1, mat2, 1000, 2); | |
| stop_time = performance.now(); | |
| console.log(`GPU Took ${stop_time - start_time} milliseconds | |
| Output:`); | |
| console.log(output); | |
| output = null; | |
| // //4 blocks of size 500 | |
| // start_time = performance.now(); | |
| // output = gpuCompute(mat1, mat2, 500, 4); | |
| // stop_time = performance.now(); | |
| // console.log(`GPU Took ${stop_time - start_time} milliseconds | |
| // Output:`); | |
| // console.log(output); | |
| // output = null; | |
| gpu.destroy(); | |
| //cpu computation. start after 1 second | |
| setTimeout(() => { | |
| //cpu computation | |
| start_time = performance.now(); | |
| output = cpuCompute(mat1, mat2); | |
| stop_time = performance.now(); | |
| console.log(`CPU Took ${stop_time - start_time} milliseconds | |
| Output:`); | |
| console.log(output); | |
| }, 1000); | |
| function cpuCompute(mat1, mat2) { | |
| let output = []; | |
| for (let i = 0; i < mat1.length; i++) { | |
| let row = []; | |
| for (let j = 0; j < mat2[0].length; j++) { | |
| let sum = 0; | |
| for (let k = 0; k < mat1[0].length; k++) { | |
| sum += mat1[i][k] * mat2[k][j]; | |
| } | |
| row.push(sum); | |
| } | |
| output.push(row); | |
| } | |
| return output; //this is going to be an array of rows | |
| } | |
| function gpuCompute(mat1, mat2, blockSize, numBlocks) { | |
| let mat1Blocks = makeBlocks(mat1, blockSize, numBlocks); | |
| let mat2Blocks = makeBlocks(mat2, blockSize, numBlocks); | |
| let output = []; | |
| for (let i = 0; i < numBlocks; i++) { //output block row | |
| let blockrow = []; | |
| for (let j = 0; j < numBlocks; j++) { //output block column | |
| let sum = []; //block sum for this output block | |
| for (let k = 0; k < numBlocks; k++) { | |
| let product = gpuMatMul(mat1Blocks[i][k], mat2Blocks[k][j]); //multiply two blocks | |
| gpuMatAdd(sum, product); //add product to sum | |
| } | |
| blockrow.push(sum); | |
| } | |
| output.push(blockrow); | |
| } | |
| return output; //this is going to be an array of block-rows where a block itself is an array of rows | |
| } | |
| function gpuMatMul(mat1, mat2) { | |
| let n = mat1.length; | |
| let kernel = gpu.createKernel(function (mat1, mat2) { | |
| let sum = 0; | |
| for (let i = 0; i < this.constants.n; i++) { | |
| sum += mat1[this.thread.y][i] * mat2[i][this.thread.x]; | |
| } | |
| return sum; | |
| }, { | |
| output: [n, n], | |
| constants: { n: n }, | |
| optimizeFloatMemory: true | |
| }); | |
| let output_gpu = kernel(mat1, mat2); | |
| return output_gpu; | |
| } | |
| function gpuMatAdd(mat1, mat2) { //adds mat2 to mat1 | |
| let n = mat2.length; | |
| let kernel = gpu.createKernel(function (mat1, mat2) { | |
| return mat1[this.thread.y][this.thread.x] + mat2[this.thread.y][this.thread.x]; | |
| }, { | |
| output: [n, n], | |
| optimizeFloatMemory: true | |
| }); | |
| if (mat1.length == 0) { | |
| //create a zero matrix mat1 with the same dimension as mat2 | |
| for (let i = 0; i < mat2.length; i++) { | |
| let row = []; | |
| for (let j = 0; j < mat2[0].length; j++) { | |
| row.push(0); | |
| } | |
| mat1.push(row); | |
| } | |
| } | |
| let output_gpu = kernel(mat1, mat2); | |
| mat1.length = 0; | |
| mat1.push.apply(mat1, output_gpu); | |
| } | |
| function makeBlocks(matrix, blockSize, numBlocks) {//divides up matrix into 'numBlocks' blocks of 'blockSize' | |
| let blocks = []; | |
| for (let h = 0; h < numBlocks; h++) { //block rows | |
| let blockrow = []; | |
| for (let i = 0; i < numBlocks; i++) { //block columns | |
| let block = []; | |
| for (let j = h * blockSize; j < (h + 1) * blockSize; j++) { //this block's rows | |
| let row = []; | |
| for (let k = i * blockSize; k < (i + 1) * blockSize; k++) { //this block's columns | |
| row.push(matrix[j][k]); | |
| } | |
| block.push(row); | |
| } | |
| blockrow.push(block); | |
| } | |
| blocks.push(blockrow); | |
| } | |
| return blocks; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment