 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
http://stellar.mit.edu/S/course/6/fa08/6.197/courseMaterial/topics/topic2/lectureNotes/Intro_and_MxM/Intro_and_MxM.pdf
--
No, Taco Bell is NOT the Mexican Phone Company!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Neeum Zawan <m.n### [at] ieee org> wrote:
>
http://stellar.mit.edu/S/course/6/fa08/6.197/courseMaterial/topics/topic2/lectureNotes/Intro_and_MxM/Intro_and_MxM.pd
f
11 operations per clock cycle on a single core - man, that's good...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I find it quite scary how they can constantly gain 2x speedups. Every
time they change something, it goes another 2x or 4x faster. You would
think that there would be a physical limit to how fast it can possibly
go, but no, it keeps getting faster without end. Hmm...
Just for giggles, I could implement this in Haskell and see how many
million times slower it is. But then, since it isn't running on the same
hardware, it would be kind of a moot comparison.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I find it quite scary how they can constantly gain 2x speedups. Every time
> they change something, it goes another 2x or 4x faster. You would think
> that there would be a physical limit to how fast it can possibly go, but
> no, it keeps getting faster without end. Hmm...
Yeh, it makes you realise that just because you think you have some "fast" C
code, there is probably still some big speedups to be made.
Next assignment, do the same activity on the inverse matrix function :-)
> Just for giggles, I could implement this in Haskell and see how many
> million times slower it is.
I wonder if it would finish in one day? :-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I find it quite scary how they can constantly gain 2x speedups. Every
>> time they change something, it goes another 2x or 4x faster. You would
>> think that there would be a physical limit to how fast it can possibly
>> go, but no, it keeps getting faster without end. Hmm...
>
> Yeh, it makes you realise that just because you think you have some
> "fast" C code, there is probably still some big speedups to be made.
I find it particularly disturbing that merely changing the order in
which the bytes reside in memory produces a 50x speedup. This
practically guarantees that no high-level programming language can ever
be fast. It means that abstraction and maintainability will forever be
the enemies of performance and efficiency.
Also... It's an 8-core server, but parallel processing gives only a 3.5x
speedup? That's pretty interesting. ;-)
Question: How much faster does this go on the GPU? [I'm going to stick
my neck out and say it'd take longer to transfer the data to the GPU
than to actually do the calculation.] Do any current GPUs support
double-precision yet?
> Next assignment, do the same activity on the inverse matrix function :-)
Hehehe, yeah... I'm guessing that's going to be a tad slower. ;-)
>> Just for giggles, I could implement this in Haskell and see how many
>> million times slower it is.
>
> I wonder if it would finish in one day? :-)
Well, the initial version took "only" 5 hours on a dual quad-Xeon 3.15
GHz server. How slow can it possibly be on my ancient 32-bit single-core
AMD Athlon 1700+ 1.5 GHz? :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I find it particularly disturbing that merely changing the order in which
> the bytes reside in memory produces a 50x speedup.
If you get the bytes in the "wrong" order then the CPU is going to be
stalled the whole time waiting for fetches from normal RAM. Get them in the
"right" order and the CPU can whizz through at full speed, while the cache
is updated almost in parallel from normal RAM.
> This practically guarantees that no high-level programming language can
> ever be fast.
Surely the compiler just needs to be a bit clever about how it does stuff?
> Question: How much faster does this go on the GPU? [I'm going to stick my
> neck out and say it'd take longer to transfer the data to the GPU than to
> actually do the calculation.]
According to Wikipedia the PCIx bus is 1064 MB/s, but I don't know if that
would be the limiting factor or not.
Anyway I found this:
http://graphics.stanford.edu/papers/gpumatrixmult/
It seems that an ATI X800XT can beat a P4 3GHz, but I have no idea how
today's latest hardware would work out.
> Do any current GPUs support double-precision yet?
Not very many, only really on the ones focussed for non-graphics work.
>> Next assignment, do the same activity on the inverse matrix function :-)
>
> Hehehe, yeah... I'm guessing that's going to be a tad slower. ;-)
But also an important part of lots of simulation software.
> Well, the initial version took "only" 5 hours on a dual quad-Xeon 3.15 GHz
> server. How slow can it possibly be on my ancient 32-bit single-core AMD
> Athlon 1700+ 1.5 GHz? :-P
I think the initial version was only using a single core. Also does Haskell
do any of the optimisations at all mentioned, or is it basically going to be
comparable performance to the initial version?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I find it particularly disturbing that merely changing the order in
>> which the bytes reside in memory produces a 50x speedup.
>
> If you get the bytes in the "wrong" order then the CPU is going to be
> stalled the whole time waiting for fetches from normal RAM. Get them in
> the "right" order and the CPU can whizz through at full speed, while the
> cache is updated almost in parallel from normal RAM.
Oh, sure, I understand *why* this happens. But it is very, very
disturbing to realise that just doing the same instructions in a
different order, or storing the same data in a different order, can have
such a vast effect on performance. It seems we have reached an age where
the complexity class of an algorithm is almost irrelevant, and the only
important property is the specific low-level details of exactly how the
algorithm has been implemented on a specific hardware platform.
This is the antithesis of high-level programming.
>> This practically guarantees that no high-level programming language
>> can ever be fast.
>
> Surely the compiler just needs to be a bit clever about how it does stuff?
Sure. Because working out what order an arbitrary program wants to
access its data in is not, in any way, equivilent to the halting
problem. No sir!
Of course, matrix multiplication is a trivially simple task. (That's why
they chose it.) But now consider building a huge, highly complex program
that does a crapload of numerical work, and trying to figure out where
the hell the performance is going, and how to fix it... Good luck with that.
>> Question: How much faster does this go on the GPU? [I'm going to stick
>> my neck out and say it'd take longer to transfer the data to the GPU
>> than to actually do the calculation.]
>
> According to Wikipedia the PCIx bus is 1064 MB/s, but I don't know if
> that would be the limiting factor or not.
>
> Anyway I found this:
>
> http://graphics.stanford.edu/papers/gpumatrixmult/
>
> It seems that an ATI X800XT can beat a P4 3GHz, but I have no idea how
> today's latest hardware would work out.
Hmm, interesting...
>> Do any current GPUs support double-precision yet?
>
> Not very many, only really on the ones focussed for non-graphics work.
Right, OK.
>>> Next assignment, do the same activity on the inverse matrix function :-)
>>
>> Hehehe, yeah... I'm guessing that's going to be a tad slower. ;-)
>
> But also an important part of lots of simulation software.
I'm not disagreeing. ;-)
>> Well, the initial version took "only" 5 hours on a dual quad-Xeon 3.15
>> GHz server. How slow can it possibly be on my ancient 32-bit
>> single-core AMD Athlon 1700+ 1.5 GHz? :-P
>
> I think the initial version was only using a single core.
No, *all* the versions except the final one were using only a single core.
> Also does
> Haskell do any of the optimisations at all mentioned, or is it basically
> going to be comparable performance to the initial version?
Depends.
Would you like me to use lists, immutable arrays, mutable arrays,
unboxed arrays or parallel arrays? Should I use 2D arrays or 1D arrays?
Should I allow integers or doubles, or stick to only integers?
Much like in Java or C, there are multiple ways you could code this in
Haskell, each with different benefits and drawbacks. (E.g., I can
practically guarantee that using single-linked lists will be
astronomically inefficient in time and space...)
Haskell offers some interesting possibilities not available in Java or
C. For example, Haskell has lightweight threads, and primitives for
"easily" turning sequential code into parallel code. It also has
parallel arrays, which are pretty much designed specifically for this
exact kind of problem. [Then again, I don't have a multicore box...]
It might be interesting to see how fast I can make this. It's kind of a
pitty I can't run their code on my PC for comparison, but I think if I
can make Haskell do the same task in under a second I'll be happy.
(Hmm. Their fastest single-core implementation takes 0.5 seconds, on a
leading-edge 3 GHz processor. Maybe expecting > 1 second on an obsolete
1 GHz CPU is asking too much?)
In particular, parallel arrays do freaky things with memory layout which
are supposed to improve performance. Be interesting to see if it
actually works at all, even on a single-core box...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Of course, matrix multiplication is a trivially simple task. (That's why
> they chose it.) But now consider building a huge, highly complex program
> that does a crapload of numerical work, and trying to figure out where the
> hell the performance is going, and how to fix it... Good luck with that.
Even in huge programs the bottlenecks are often only due to a tiny
proportion of code running a vast number of times (for instance, I am pretty
sure almost all of the CPU time for my CFD solver is spent inverting
matricies). Compilers are already quite good at optimising such things, but
it appears they can still do a lot more. For example they already can spot
fairly basic patterns in read and write locations and rearrange the
instructions to give better performance, adding more complexity just means
more work for the compiler writers and handling more special cases. Whether
anyone can be bothered though is another matter...
> Would you like me to use lists, immutable arrays, mutable arrays, unboxed
> arrays or parallel arrays? Should I use 2D arrays or 1D arrays? Should I
> allow integers or doubles, or stick to only integers?
You could do a similar exercise to what the guy did. Start off with a
really "obvious" way of doing it, then try out different things and time
each one. Make a nice list like he did showing how much faster you can make
it than the "initial" version.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Of course, matrix multiplication is a trivially simple task. (That's
>> why they chose it.) But now consider building a huge, highly complex
>> program that does a crapload of numerical work, and trying to figure
>> out where the hell the performance is going, and how to fix it... Good
>> luck with that.
>
> Even in huge programs the bottlenecks are often only due to a tiny
> proportion of code running a vast number of times (for instance, I am
> pretty sure almost all of the CPU time for my CFD solver is spent
> inverting matricies). Compilers are already quite good at optimising
> such things, but it appears they can still do a lot more.
I suspect few compilers are going to detect that you should transpose
one matrix while performing matrix multiplication just by inspecting the
souce code for the matric multiplication function.
Interestingly, in Haskell you could do something like
matrix_multiply x y = core_multiply x (transpose y)
and then do something like
{-# RULES "transpose^2" transpose . transpose = id #-}
What this does is everywhere the compiler sees a matrix being transposed
twice, it automatically removes the transpositions. So if you multiply
two matricies and one of them is *already* transposed, matrix_multiply
won't bother transposing it again. It just gets passed to core_multiply
unchanged.
You could store certain matricies permanently transposed, and then
transpose them back just before passing them to matrix_multiple. The
compiler will optimise out the transpose operation automatically. And
all this without needing to modify the compiler to add a special
optimisation pass; it's just some plain ordinary Haskell source code.
>> Would you like me to use lists, immutable arrays, mutable arrays,
>> unboxed arrays or parallel arrays? Should I use 2D arrays or 1D
>> arrays? Should I allow integers or doubles, or stick to only integers?
>
> You could do a similar exercise to what the guy did. Start off with a
> really "obvious" way of doing it, then try out different things and time
> each one. Make a nice list like he did showing how much faster you can
> make it than the "initial" version.
Indeed, this is my plan. I'm just trying to get the naive list-based
version to work. (Currently it gives the wrong answers, which obviously
isn't a lot of use...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Indeed, this is my plan. I'm just trying to get the naive list-based
> version to work. (Currently it gives the wrong answers, which obviously
> isn't a lot of use...)
I could have written a working C version by now :-D
Also I wonder how his results compare to something like MatLab that
supposedly has very fast matrix handling functions built it...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Indeed, this is my plan. I'm just trying to get the naive list-based
>> version to work. (Currently it gives the wrong answers, which
>> obviously isn't a lot of use...)
>
> I could have written a working C version by now :-D
I have a working Haskell version by now. (Apparently I mixed up the rows
and columns, hence the bogus answers.) It's really not hard. I've
actually spent more time building a test harness than coding the matrix
multiplication so far.
In case you care, the code is:
type Matrix x = [[x]]
multiply :: (Num x) => Matrix x -> Matrix x -> Matrix x
multiply m1 m2 = [ [ sum $ zipWith (*) row col | col <- transpose m2 ] |
row <- m1 ]
That's the whole program. (Minus the part where it creates some
matricies, multiplies then, and prints out the result.) Complex, eh?
Now, in terms of speed... Well, it takes about 62 seconds to multiply
two 512x512 matricies. But hey, this is only the simplest, dumbest
version I could come up with. Let's see what happens (if anything) when
I start applying a few optimisations...
> Also I wonder how his results compare to something like MatLab that
> supposedly has very fast matrix handling functions built it...
Well, matrix multiplication is a built-in MatLab primitive. I would
imagine it's comparable to BLAS (or possibly parallel BLAS)...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible a écrit :
> It seems we have reached an age where the complexity class of an
> algorithm is almost irrelevant, and the only important property is
> the specific low-level details of exactly how the algorithm has been
> implemented on a specific hardware platform.
>
> This is the antithesis of high-level programming.
Actually the complexity class of the algorithm remains exactly as
relevant because it just says how the computation time asymptotically
evolves as the data gets bigger. The optimization described here do not
change that I believe. Just the multiplicative constant in front, which
in practice is of course important as well ;-)
--
Vincent
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 07/23/09 04:19, Invisible wrote:
> Just for giggles, I could implement this in Haskell and see how many
> million times slower it is. But then, since it isn't running on the same
> hardware, it would be kind of a moot comparison.
Well, they _do_ provide the source...
--
No, Taco Bell is NOT the Mexican Phone Company!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 07/23/09 05:42, Invisible wrote:
> This is the antithesis of high-level programming.
As is all numerical computation.
--
No, Taco Bell is NOT the Mexican Phone Company!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Vincent Le Chevalier wrote:
> Actually the complexity class of the algorithm remains exactly as
> relevant because it just says how the computation time asymptotically
> evolves as the data gets bigger. The optimization described here do not
> change that I believe. Just the multiplicative constant in front, which
> in practice is of course important as well ;-)
I think that BLAS probably uses a slightly more asymptotically efficient
multiplication algorithm for matrices this size, but it's interesting
that at best it only accounts for a small fraction of the speedup.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Oh, sure, I understand *why* this happens. But it is very, very
> disturbing to realise that just doing the same instructions in a
> different order, or storing the same data in a different order, can have
> such a vast effect on performance. It seems we have reached an age where
> the complexity class of an algorithm is almost irrelevant, and the only
> important property is the specific low-level details of exactly how the
> algorithm has been implemented on a specific hardware platform.
>
> This is the antithesis of high-level programming.
>
Was an example if this I saw recently with multi-core programming. If
you changed the memory "directly" which was used between multiple
threads in the program, then all cores would have to wait for the
"current" core to finish handling the data, thus unlocking the memory,
so that the other cores would operate. The result would be that every
single core would be wobbling between wait and active, and your speed
would drop *under* that of a single core working on the same process.
The fix was simple. Make your function so you pass the value (not a
pointer), handle it internally as a temporary variable, then return it,
where the calling function would only set the value. The memory would be
free while the function was being called and executing, and only "lock"
during the brief moment the final value was set. Result - the expected
increase in speed, as you increase the number of cores.
Yeah, one they got to multi-core, the idea of, "The language doesn't
need to know anything about the hardware.", was lost, to some extent.
But, then, you also get stupid things like GCC optimizing out NULL
tests, which actually caused two Linux kernal versions to suffer a
potential, Windows style, "root level access no matter what account you
are on", problem. The compiler needs to be smart enough to "know" you
are compiling for multi-cores, and warn you about such things (or avoid
optimizing in a way that causes them). But, high level languages where
all developed "before" this was an issue, so its not surprising its
shown up now.
--
void main () {
If Schrödingers_cat is alive or version > 98 {
if version = "Vista" {
call slow_by_half();
call DRM_everything();
}
call functional_code();
}
else
call crash_windows();
}
<A HREF='http://www.daz3d.com/index.php?refid=16130551'>Get 3D Models,
3D Content, and 3D Software at DAZ3D!</A>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Patrick Elliott wrote:
> The compiler needs to be smart enough to "know" you
> are compiling for multi-cores, and warn you about such things (or avoid
> optimizing in a way that causes them).
More precisely, the compiler needs to "know" what your processes are,
instead of leaving it as an opaque library outside the semantics of the
language completely. See the ongoing thread elsewhere. ;-)
--
Darren New, San Diego CA, USA (PST)
"We'd like you to back-port all the changes in 2.0
back to version 1.0."
"We've done that already. We call it 2.0."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Sure. Because working out what order an arbitrary program wants to
> access its data in is not, in any way, equivilent to the halting
> problem. No sir!
Remember, the Halting Problem is unsolvable in the general case, but may
be solvable in specific cases.
It's the same thing with compiled code. While the compiler can't
guarantee that *every* code file will be compiled to its optimal machine
code, it can guarantee that *sets* of code files will. The job of the
compiler developer is to identify these potential sets, and teach the
compiler to recognize them.
--
Chambers
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> The compiler needs to be smart enough to "know" you are compiling for
>> multi-cores, and warn you about such things (or avoid optimizing in a
>> way that causes them).
>
> More precisely, the compiler needs to "know" what your processes are,
> instead of leaving it as an opaque library outside the semantics of the
> language completely. See the ongoing thread elsewhere. ;-)
And I would suggest that geniunely "high-level" languages (i.e.,
languages were you don't manually frob low-level machine resources) have
a much greater chance of adapting to multicore programming...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
