Multi-Dimensional Data (as used in Tensors) - Computerphile
Vložit
- čas přidán 6. 02. 2020
- How do computers represent multi-dimensional data? Dr Mike Pound explains the mapping.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
![[실시간] 전철에서 찍힌 기생생물 감염 장면 | 기생수: 더 그레이](http://i.ytimg.com/vi/4nkFvwxGAfA/mqdefault.jpg)
"We need bigger paper". The whiteboard behind him: "am i a joke to you"
Someone get him some brown numberphile paper
Golden rule is to use powers of 2 as sizes, then you get away with bitwise shifts instead of multiplying. So for a 100x100 dataset, you want to set up a 128x128 grid, then you can address each row by R SHL 7, an instruction done in a single clock cycle, instead of a MUL which afaik takes longer on every platform. You wasted quite a lot of storage, but you gain precious speed.
It's kinda yes and no.
Shifting is faster than multiplying. But adding paddings make the access pattern more complex leading to more cache misses. Which are far more expensive.
Also, unless you are JITing or compiling, you need your library containing the optimization and detecting at runtime. Which may not be the case.
That is kind of inefficient. Imagine the same done for 5d. Your matrix is suddenly more than 3 times larger.
@cas curse Or if you're writing something that does not need to be optimized. Spending ages trying to optimize some code that'll only be run once every hour or so can be rather pointless.
@cas curse As long as your code is not idioticly unoptimal, these kind of optimizations are loss of time. Instead of thinking about the problem at hand, you think about all the itsy bitsy low level trickery to make it, what, 5% faster.
TL;DR If performance is critical (you work in HPC, aviation, automobile, game, etc.. ) You design the performance into your code. You consider the performance implications in the first place. Sometimes even 1% of performance make or breaks stuff in these industries.
On the other hand, if performance is something you can easily get by scaling out (Web/Mobile App, low volume) or you know your code only takes like 0.1% percent of time in the system anyway (Language Wrappers, Function interfaces, one-off program). You build the thing then maybe optimize it. Then buy more computers.
Glad you mentioned doing the clever things another time.
Makes me really excited about possible seeing a video on cache optimization, like interlacing the memory and such.
Me too! I'd like that
Seconded
Yes
I'm curious whether "swizzling" as it's called is used in ML. Or if it's just a graphics thing.
@@MooseBoys42 probably both, as ML and graphics have a lot of _parallels_
piece of art for editing. THANK YOU
I see Mike; instant like
I too am a simple man
It’s a shame I can only give this video a one dimensional “like”
Zero dimensional boolean, I wish it was a whole dimension :-D
Actually it is 2 dimensional as the like button is an image ;)
Whether boolean is its own dimension or not, its a shame you're getting 1 dimensional comments from an n-dimensional language space 😂😂😂
@@_adi_dev_ Agreed :-D
Fascinating, as always. But when you said storing that bitmap as anything but a 1D array didn't make sense ... now I have an urge to implement 2D storage on a disk drive using track as x and sector as y.
It's funny that we use row/column addressed hardware which does a transform to make it seem linear for programs which then transform those addresses back into row/column.
Dr £ is an excellent explainer of pretty much anything.
When I was doing stuff like this back in 2010, I too ended up thinking about the deminsions as sets, or groups, of other sets. I never used strides though, Instead I just itterated through the needed parts of the multi dimensional array. In my mind it was the same as spinning through a rubrikscube with many more sides, only checking the appropriate corners for information.
I guess I was using "tensors" all this time then, since I would say "look at the top left pixel, in the blue layer for the first set of images" by fixing the "set", "layer" and "pixel" and then looping through "images", which is the same as feeding in a bunch a stride commands formed as tensors.
i was already subscribed of the channel, i am a programming student , i just realized by my self that this was possible, and here i am finding confirmation of my hypothesis.
APL was a multi-dimensional array language invented by Ken Iverson at IBM research in the early '60s. It was an early interpretive langage, and was extremely useful in doing anything involving arrays. I loved it! of course, I had a math degree and was comfortable with linear algebra etc. I used it to simulate computer architectures, compute project timelines and risks, model animal behvior, and otherwise have a good time! It had its own obscure set of symbols representing array operations, and was affectionately known as "a write only language", which is probably why it did not catch on.
That's the one you needed a special keyboard for, right? That probably didn't help! (Yes, yes, overlays, just learn to touch type ...)
A major advantage arising from keeping everything contiguous in memory is of course cache coherency. This is more significant than the "no need to copy data" explanation given because if were to construct multi-dimensional data from pointers to pointers we would still have that property and also be able to have differing sizes per dimension (jagged arrays). We would however have any lost cache coherency guarantees.
"Numerical Recipes" book, from which I studied numerical computing in university, uses arrays of pointers to arrays of pointers...to actual data. I think a few multiplications are a lot better on modern machines, where processors are many times faster than memory...
How many people tried to wipe the two dots on the whiteboard (in the medium shot) off their screen only to realize they were part of the image?
I had a sense of how this might work but never looked under the hood and it didn't really click for me until mike said he visualizes higher dimensional data structures as "groups of groups..." which totally makes sense
You should do a show on the methods used when storing large image sets like for sky surveys and particle physics. Because the files are so large and one only wants to see a portion of the image efficiency of retrieval is needed. Spoiler, the images are stored so that pixels near each other are near each other in memory. I am trying to remember who gave the talk I found got this from. I think it might of been Dr. Mark SubbaRao from the Adler Planetarium or someone from Fermilab. The solution if I remember correctly is to have the offset being the element parameter of a space filling curve.
Cool! This might be useful for something I have been struggling with. If you recall, let me know!
If contiguous data is important for performance, this implies that performance of operations would depend heavily on which way you need to slice the data. I would imagine there are cases where it you need to work along different dimensions. I'm wondering how much of a difference this makes to performance and also if there are any techniques to mitigate this?
Great video, thanks!
Inteliigent explanation. Where are you from ?
Thank you! Pls. more!
Before watching, I'm going to say array dims aligned to powers of 2 and shifts instead of multiplies. Arranging data so you can work on the last dim in parallel would help lots too.. sparse/ragged arrays for large data sets.. All native screen resolutions should be powers of 2 also... ideally... by law!...
after watching... ahhh, the basics, but well said. Shifts are 2 to 4 times faster than multiplies and use much fewer Watts.
Peter parker of image processing ! , thank you spidy :)
Good on ya Mike
Dr Mike pound!!
wouldn’t it be more efficient to store all channels of an image in a, for example, int array and then use bitwise AND to get the individual color information from those ints instead of having one char array for each one?
Good stuff
That is basic practice for every APL / J / K programmer for several decades now. Even with big amounts of data.
Yess!!!
How does this get optimized in relation to cpu cache?
Wanted to ask this too. I think, that rgb should be the first dimension, since these will most likely be accessed together, so they can be loaded into the same cache line.
For 100 px by 100 px I think they will be on the same cache line, but I don't think this method scales up for bigger images
Tiling, essentially. Put a maximum tile size on each dimension such that the whole tile (or several) fits in cache, then essentially treat tile number as another dimension in this system.
@@serkanmuhcu1270 Although, your intuition is somewhat correct, the real answer is slightly more complicated. NHWC vs NCHW (where N is batch, H and W are width and height and C is channel) is a somewhat controversial question, so most frameworks offer both versions and allow the programmer to choose.
Even better, many frameworks actually use abstractions, which hide the real layout of data and just measure the actual performance in different configuration and choose the best one before running your code. This is the best approach, since the efficiency of different approaches can depend in complicated, unpredictable ways on the network architecture, hardware used, the size of the data and even what other applications are currently running on the system. There is no "one-layout-fits-all" approach, so it's best to select the best one for each case automatically.
The graphic demonstrating Y stride is wrong. Brady, what number do we start with?, and remember, we're not doing a numberphile video.
If the total number of elements in a 1D array is a square (for 2D array) or a cube (for a 3D array), etc, can’t you use DIV and MOD values of the index of the array to switch between a multi-dimensional array and a 1D array?
Example: 1D array has 100 elements, or 10^2
Convert into a 2D element and find 32th element in 1D array:
32mod10 = 2 (i.e. 2nd column of 2D array)
32div10 = 3 (i.e. 3rd row of 2D array)
Reverse operation:
(3 x 10^1) + (2 x 10^0) = 32 (element in 1D array)
Yep. Thats more or less how its done
I say shear is the way to go
MichaelKingsfordGray If you don’t know the answer, then don’t bother commenting.
Mathematically, yes, that would be correct. However, why would you need to switch from 1d to multi-d ? It's always the other way around.
Good one.
This video was so relevant to me. I'm just learning c++ and this is like definitely the best way to make multi dimensional arrays.
At 6:15, don't you mean you need more dimensions on you paper?
Very Nice
WHY CAN'T I HOLD ALL THESE DIMENSIONS? 😱
I have just started my way on image processing, and the way I figured it is to use a "pixel structure" that stores the RGB values of each pixel, so I just had to use a 2D array to store every pixel, making my life a little bit simple... so, can someone tell me wich one is the best way to represent the image?, am I wasting memory/speed?, what could I do to improve on that?
The number of elements is still the same; the way you address the data doesn not magically change the amount of data. The only place you'd possibly see a difference in speed is in the complexity of the operations you use to address specific pixels, which only really becomes a concern on a per-language basis. Fortran for instance still sees use today thanks to its array-handling features.
As far as image-processing goes, I know OpenCV stores image data in the way you've described it by default - an MxN matrix of arrays of length 3 that each represent a pixel, so I personally don't see much benefit in deviating from it since its library functions are designed around it. It's better to look into the specifics of the language and library you're using to get a better idea about what practices you should be inculcating.
I'm not expert on the subject, mind you. I just started image-processing and CUDA last month so that's all I really feel confident in saying. Cheers!
Better seeing this from algorithm and data structure point of view
awesome
What is an "awway"?
Intuitively it sort of makes sense, but in terms of details I don't understand the efficiency gains of one contiguous array vs multiple nested arrays. Using a 2D-array as an example, wouldn't multiplying the y-stride by the x-stride followed by the lookup be just as fast as using constant values to each perform a lookup? Not familiar with the overhead involved in array lookups, I suppose.
Hopefully you'll get an answer to this. :)
Great question! There will be some cache lookup benefits to having it all stored together, which is less likely with jagged arrays. Mainly though it comes down to when you're doing block copies and stuff.
In the case where you're looking up a single pixel, the speed benefit will be negligible. When this approach will really shine is when you say "copy me all the data from dimension 4 indexes 4 to 7", where the whole block is contiguous. In this case there will be the single initial lookup, and then just read the whole thing at once.
Itll also be a lot easier this way to take "slices" e.g. half of an image, but I didn't really say much on this yet due to time constraints!
Well if you're looping through a 2d array, the most obvious thing to do is a nested for loop, but from that you get extra overhead from loop control. Now if you imagine that scaled up to many dimensions, just have a 1d loop and a 1d array, and you do away with most of that overhead.
I can't be too sure, as it depends on languages and compiler optimisation, but sometimes the handling of >1D and 1D arrays are different in memory and machine code, and sometimes the same. I think the video is more about my first point, where loop flattening can make a big difference.
At the lowest level of programming all arrays are long sections of memory. So 2D array as x y is a section of memory which is x*y long. The constants are used to calculate the offsets to get the right value. With more dimensions there are more constants to calculate the offsets. Using constants means that you don't need to calculate fixed values all the time and so is quicker than doing extra maths.
AFAIK he's mostly just talking about how computers, in general, handle multi-dimensional arrays. If you use a higher-level language to work with multi-dimensional arrays, this is what the compiler/interpreter will be doing behind the scenes, to make it appear to be a multi-dimensional array. However, there are some occasions where the programmer may be forced to do these sorts of things explicitly.
That does not seem that dynamic to me, how would you go on store for example words ? Would you reallly go on allocate space for the possible characters at each new instance, and how to tell a word is ending would not something like a file allocation table be more efficient. Or maybe an algorith of ones own, that search thru a tree, or do you say it would be to slow?
I mean chess moves could be stored in a folder structure, now there is depth restrictions, but one could possibly come up with something that basically alllow you to store a datastructure of a few terrabytes, and with unlimited depth to store any kind of forked data structures?
Isn't that basicly how alpha zero works?
Well for chess you would need two structures one where white is winning and one where black is winning
And then it is basicly just about set up the rules for the game and let it play, as i understand it alpha zero have no idea of the value of pieces to start with? At some point you remove futile paths "moves" for the players.
Probably you do not let it play all moves from beginning, just 10 and then evaluate the positions. Next you play 20, 30 and so on until a full game played thru. Next you revise structure by play 5,,15,25 before evaluation and see if other patterns have emerged in evaluation.
@@JmanNo42 No an expert in AI, are you saying that all possible moves are coded in an conventional chess program? Whereas alpha does that dynamically?
@@kkgt6591 Well i do not know i assumed that alphago wrote to file dynamically, not allocated all possible positions for each move, i mean that would not be much depth/dimensions of such a tree?
My understanding of chessprogram is that they do not store that much except for in memory, maybe 5 and six moves and evaluate constantly?
And then they have the opening book stored, whille i thought that alpha go stores succesful "winning" games. And then cut of branches that do not look successful. And that they hare stored in a "linear" searchable tree/file. structure much like a file allocation table.
I would like to know computational cost of convolution (on the context of convolutional NN).
On a two dimensional array, like an image, it is O(image pixel count x convolution brush pixel count) in general.
@Riccardo Orlando
That is complexity of trivial algorithm, but I would like to know more about the lower bound.
@@woowooNeedsFaith From what I can tell, lower bound is n*log(n). At least that's the limit for linear convolution, because it can be implemented as multiplication in frequency domain ( O(n) ) and conversions from and to frequency domain can be done via FFT. FFT is O(n*log(n)) and is proven to be the fastest possible way to do it.
How does sparse data get stored and accessed?
Littleton
But you are thinking in pixels instead of voxels. Assign colors to axis instead of levels.
I did some work on this leading to a 13th dimensional, multi-base computer.
Project oracle the computer that imitates reality.
Takes me right back to my last year in Comp Sci. I used many techniques like this and vectorized loops etc. to build a 3-d laser scanner and associated reconstruction software. Then I left University and never made use of my degree at all........I wish I'd just stayed in the University to be honest - but oh no - get out into the real world I was told.......why do I listen to other peoples advice?
I think you could go back to university. Doing things you don't like will make you bitter in the long run...
I wonder if I could mail him a question and we could have a conversation on it
Every number could be imagined as existing in the dimensionality of its digits. The stride would be the power of the base for the unit place. We've been using multiple dimensions all along.
"Nifty" Are you even allowed to say that 'over there?' ;)
When is Nottingham going to run out of that 1980s printer paper?
the second video on multi-dimensional data
I've still got three cases of blue-bar paper in my garage.
kinda weird to call matrices tensors. Where does that come from?
Real mathematicians dont call multidimensional arrays as tensors
And now we understand why languages that don't have linearly places array memory die a timely death when dealing with large arrays :D
@MichaelKingsfordGray Guess it depends on the implementation? I know for Javascript everything in an array is really just an object that is hashed, making for easy access to elements and potential savings on memory for sparse arrays at the sacrificed of speed...quite a bit of speed. I know more mathy libraries exist for things like python, but they are beyond my knowledge!
Paper overflow!
More paper ?
You have a huge whiteboard right behind you.
More ecological too :p
Computerphile paper is all left over from years ago so any impact on the environment has already been done, might as well use it.
Some even say the very reason this channel exists is so that they can get rid of all that paper...
brzrkr still would have prefered if in some cases they would use the whiteboard, like more complex ones like this video.
@@555Devil555 Yeah I agree. Sometimes extra space is needed.
Why don't they use the whiteboard right behing him instead of wasting paper??
Growing new trees reduces carbon more than keeping trees alive. Uses less water, too.
Geez, I think this could've been made clearer. What's a channel? What does the data look like in memory, or what would it look like on a straight line?
too tired to understand anything but I'll come back i recon
💯
I think TensorFlow hates me...
Try pytorch. Its the way to go now
Wait am I missing something? Isn't this what is explained in a basic C course?
okay boomer
I'm finally getting around to pronouncing Euler as "Oiler", but NumPy is still "Numb-pee" to me.
you're not alone
@@existenceisillusion6528
Cuppy
(A cup that is a pet)
Yeah, I definitely read it as pee rather than pie.
@@existenceisillusion6528 I read that as Q-pee
@@danieljensen2626 KooPie
It all goes back to that infinite length of tape.
See also: why it's stupid and crazy that MATLAB let's you dynamically change the size of multi-dimensional arrays.
Well, to be fair, it gives a warning whenever you do that.
I feel like this video could have been a minute long. Like I get it, it works just as well for more than 2 or 3 dimensions
Was there any information in this video? I was waiting for any sort of trick or something
It was a pop quiz to see if you recognized inaccurate graphical explanations. I guess you didnt. Fortunately, actual ability and ability to condescend are inversely proportional
@MichaelKingsfordGray Lecture, go on. At worst I chastened, rather more an admonishment.
And what sort of android-pretending-to-be-human-phrase is "real adult name "? I'm legitimately concerned you might be having a stroke right now.
@@Mr.Beauregarde "...rather more an astonishment."
"I'm legitimately concerned you might be having a stroke right now."
@@theyaoster I'm astonished you'd admonish what's so clearly a #dyac moment.
y×width+x
Javidx9 anyone?
It is very much NOT just javid. Altough, he is an amazing programmer.
Zero Cool Fully understood and agreed, I just like using these little connections to toss the names of people I like in the comments so others will hopefully see them and go subscribe.
Mike, you need to get some deep! Im worried about you.
Some deep what?
what
unnecessarily redundant way of teaching. in 10 minutes you could also talk about ways of storing values in scarce tensors (like hashing dimension indexes etc.).
Last time i was this early...
JK I was never this early 😂
You're using paper and run out of room.... Why not use the marker board to your left?... Save the paper for something worth the tree. 😁
Pure gibberish what was he talking about, that man needed a script or something.
When I watch numberphile I hear lots of new interesting stuff. When I watch comouterphile it is always 100% something I knew/learned as a teenager... dissapointing
r/iamverysmart
Oddly elementary, this one.
That's not tensors, that's just basic pointer arithmetic, c'mon, up the voltage!
Nearly first
so?
Well sorry i bothered… very confusing output of such a simple process… He is childish in his organizational ability… waste of time
Who is from /g/ or /tech/?
/sci/