Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Build a Neural Network

enlight.nyc

Post reply on HN
Print view View original

21–30 of 49 posts

Re: Build a Neural Network

#21

Post by pilooch »

fartcannon wrote: post #2

As someone who has read a lot of implementing neural networks from articles, the massive problem with all of them is that they import numpy. You may think that it is silly to reimplement the matrix math but with out that part of the code, you can't easily port it to other languages/microcontrollers/microwaves/badgers. It's a legitimately valid part of machine learning, and its not easy to do for novices. And I need h…

Exactly the reason why my colleagues and myself do all deep learning in C++, performance and portability, from cloud to RPie. We've even modified caffe2 so we could build the training graph from pure C++. We know this is not the current doxa :) It's also all open sourced just in case others might need it...

Re: Build a Neural Network

#22

Post by felipellrocha »

fartcannon wrote: post #2

As someone who has read a lot of implementing neural networks from articles, the massive problem with all of them is that they import numpy. You may think that it is silly to reimplement the matrix math but with out that part of the code, you can't easily port it to other languages/microcontrollers/microwaves/badgers. It's a legitimately valid part of machine learning, and its not easy to do for novices. And I need h…

Yep. I would like to see an article that implements everything without using matrices first, then creates the matrices library with you, and refactors everything over.

So much learning that we're missing by not going through this step.

Re: Build a Neural Network

#23

Post by johndough »

asdfman123 wrote: post #18
gnulinux wrote: post #9

Earlier quoted context omitted.

Matrix math is easy peasy. Freshman level programming. Just lookup algorithms on Wikipedia and you're all set. The problem is it's extremely hard to make it efficient. Dozens of men-years are spent trying to optimize linear algebra libraries. There are handful linalg libraries that have competitive performance. It was my college project to make a fast linalg library, and boy it is fast. There are some things like mat…

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

The answer is: No one really knows because cuBLAS is closed source.

But to get within the same order of magnitude, tiling the workload for better cache utilization is usually the most important step. This article [1] explains it quite well and also lists a few other tricks.

In addition, there's also the fast Fourier transform for large filter kernels and Winograd convolutions [2] for small filter kernels.

[1] https://cnugteren.github.io/tutorial/pages/page1.html

[2] https://arxiv.org/pdf/1509.09308.pdf

Re: Build a Neural Network

#24

Post by keerthiko »

asdfman123 wrote: post #18
gnulinux wrote: post #9

Earlier quoted context omitted.

Matrix math is easy peasy. Freshman level programming. Just lookup algorithms on Wikipedia and you're all set. The problem is it's extremely hard to make it efficient. Dozens of men-years are spent trying to optimize linear algebra libraries. There are handful linalg libraries that have competitive performance. It was my college project to make a fast linalg library, and boy it is fast. There are some things like mat…

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

You can look at the basic algorithm on wikipedia[0], and you'll see that a lot of it is parallelizable (non-sequential dependency of calculations) which by default is easily (time-) optimized via GPU pipes.

After that, there are some caching optimizations to be had by iterating over the nested loops to minimize cache misses. Another optimization is to split up the matrices if their shapes are appropriate and use compounding matrix operations to recombine them, allowing for further use of parallelization in phases.

There are a few fancier algorithms out there which are optimized for certain assumptions -- extremely large matrices, several consecutive operations, matrices with many 0s or many identical entries or following certain patterns for values such as the identity matrix or eigenvectors, etc.

[0] https://en.wikipedia.org/wiki/Matrix_multiplication

Re: Build a Neural Network

#25

Post by eindiran »

asdfman123 wrote: post #18
gnulinux wrote: post #9

Earlier quoted context omitted.

Matrix math is easy peasy. Freshman level programming. Just lookup algorithms on Wikipedia and you're all set. The problem is it's extremely hard to make it efficient. Dozens of men-years are spent trying to optimize linear algebra libraries. There are handful linalg libraries that have competitive performance. It was my college project to make a fast linalg library, and boy it is fast. There are some things like mat…

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

On the CPU, matrix multiplication follows the same procedure you'd use to multiply matrices by hand. But GPUs are good at performing the same operation on a bunch of data at the same time. Any operation that is embarrassingly parallel is a good fit for doing on the GPU and often large matrix multiplications are. So the premise is that you do the steps that don't need to be done sequentially in parallel on the GPU.

Most approaches to doing matrix multiplication on the GPU benefit from doing operations in a way that plays off the behavior described above, make good use of caching, and respond to how the data in your matrix actually looks (e.g. is it sparse, etc).

To learn how you'd do matrix multiplication on the GPU, you might want to look up how its done via CUDA since many applications that make use of the GPU do so via CUDA and it doesn't require specific knowlege of graphics programming. This seems like a good introduction: https://www.shodor.org/media/content/petascale/materials/UPM...

Re: Build a Neural Network

#26

Post by dragontamer »

asdfman123 wrote: post #18
gnulinux wrote: post #9

Earlier quoted context omitted.

Matrix math is easy peasy. Freshman level programming. Just lookup algorithms on Wikipedia and you're all set. The problem is it's extremely hard to make it efficient. Dozens of men-years are spent trying to optimize linear algebra libraries. There are handful linalg libraries that have competitive performance. It was my college project to make a fast linalg library, and boy it is fast. There are some things like mat…

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

> Caching?

That's the first step. If you have a 64kB cache, then you want to fill that cache ONCE, calculate everything you can with that 64kB chunk of data. Save off the result, and then load a new 64kB chunk. This is called "tiling".

Its actually kinda tricky to do just right, but once you know the concept, you basically spend effort ensuring that main-memory hits are minimized.

GPUs have many different memory regions: global Memory, L2, L1, "Shared" memory, and finally registers. Maximizing your math and minimizing your memory-moves is one big part of optimization.

-------

There are a ton of other optimization tricks: GPUs are more efficient if they access memory in certain ways. "Shared Memory" in GPUs are typically banked (on modern NVidia and AMD GPUs).

If you have 64-threads, it is more efficient if thread#0 accesses X+0. Thread#1 accesses X+1. Thread#2 accesses X+2. (etc. etc.) Thread#63 accesses X+63. In fact, a GPU can perform all 64-memory loads simultaneously.

However, if the 64-threads all access memory location X+4, you have a "bank conflict". The 64-threads can only read this memory location one-at-a-time, resulting in a massive slowdown.

There are a huge number of tricks in "tricking" the for loops to access memory optimally across your many, many threads that are calculating the multiplication.

--------

> Some kind of clever mathematical tricks?

The clever mathematical tricks have been solved and are known. LU decomposition, etc. etc. Its important to know them, but that's not generally what people mean by "optimization".

Re: Build a Neural Network

#27

Post by tntn »

johndough wrote: post #23
asdfman123 wrote: post #18

Earlier quoted context omitted.

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

The answer is: No one really knows because cuBLAS is closed source. But to get within the same order of magnitude, tiling the workload for better cache utilization is usually the most important step. This article [1] explains it quite well and also lists a few other tricks. In addition, there's also the fast Fourier transform for large filter kernels and Winograd convolutions [2] for small filter kernels. [1] https:/…

Not entirely true - Scott Gray knows: https://github.com/NervanaSystems/maxas/wiki/SGEMM

IIRC his kernels shipped in cuBLAS at some point.

Re: Build a Neural Network

#28

Post by samsonradu »

melling wrote: post #3

Here's another Neural Network from scratch that I found useful: https://victorzhou.com/blog/intro-to-neural-networks/

Thanks a lot for this, it is indeed very clear and easy to follow! Good walkthrough on the partial derivatives calculations which imo are the hardest part.

Re: Build a Neural Network

#29

Post by gnulinux »

asdfman123 wrote: post #18
gnulinux wrote: post #9

Earlier quoted context omitted.

Matrix math is easy peasy. Freshman level programming. Just lookup algorithms on Wikipedia and you're all set. The problem is it's extremely hard to make it efficient. Dozens of men-years are spent trying to optimize linear algebra libraries. There are handful linalg libraries that have competitive performance. It was my college project to make a fast linalg library, and boy it is fast. There are some things like mat…

Can anyone simply explain the gist of how matrix multiplication is optimized? I know a lot of is farmed out to the GPU (if you've got a good GPU), but what's the essence of it? Caching? Some kind of clever mathematical tricks? All of the above?

Things I used in my project were:

> (vectorization, OpenMP, handwritten assembly, automatically optimized code, various optimizations, better algorithm.....)

also in addition to these, I used caching. Also GPU programming, but it's a trade-off.

Re: Build a Neural Network

#30

Post by inertiatic »

jorgeleo wrote: post #16

This tutorial explained to me at the exact level of detail: https://mattmazur.com/2015/03/17/a-step-by-step-backpropagat... It was detailed enough for me to do all the calculations in an excel workbook, 1 complete cycle (forward, backward, and forward with the learned weights) https://1drv.ms/x/s!Ar06sKFtc9d7goR5WQLo-RkB0XvWAA Which allowed me to play with the name and factors to understand better how they impact the…

Having spent a lot of time hunting for the best way to figure out backprop, that is the best resource I've found and the one that finally made everything I've read click.
Post reply on HN