| Author |
Message |
Nick Maclaren
Guest
|
 Posted:
Thu Sep 22, 2005 1:39 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <peyppsr1fsvy.fsf@pxpl2829.amr.corp.intel.com>,
Andy Glew <andy.glew@intel.com> wrote:
| Quote: | By the way, I'd love to see a proof describing what problems can be
solved efficiently with deterministic parallelism, and what no.
Assuming sufficient parallelism, is this equivalent to deciding the
set difference between P and NP?
It might be; or it might be similar to one of the other set problems.
I believe it has been proven that in some cases truly randomized or
non-deterministic automation are more efficient than deterministic. (I
don't have my theory books beside me in Israel.)
But I am not sure that the sort of nondeterminism we are talking about
here is as powerful as the nondeterminism in a non-deterministic
finite state automaton.
|
Sigh. The so-called nondeterministic automata are nothing of the
sort. They are completely deterministic and are equivalent to
what the computer scientists call deterministic ones with a single
extra primitive:
Apply function F to operand sets A(1...N) and return TRUE if
any of F(A[i])) return TRUE, but in time max(time(F(A[i])))
not sum(time(F(A[i]))).
I don't know what complete imbecile first coined that name, but he
has caused more harm by his gross abuse of terminology than anyone
else I can think of in science.
The concept of deterministic and true nondeterministic automata
and the correct use of the terms eterministic and nondeterministic
predate the computer scientists' abuse of the terms by a long way,
as I posted some time back (perhaps on comp.theory).
Regards,
Nick Maclaren. |
|
| Back to top |
|
 |
David C. DiNucci
Guest
|
| Posted:
Thu Sep 22, 2005 2:04 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Nick Maclaren wrote:
| Quote: | In article <peyppsr1fsvy.fsf@pxpl2829.amr.corp.intel.com>,
Andy Glew <andy.glew@intel.com> wrote:
By the way, I'd love to see a proof describing what problems can be
solved efficiently with deterministic parallelism, and what no.
Assuming sufficient parallelism, is this equivalent to deciding the
set difference between P and NP?
It might be; or it might be similar to one of the other set problems.
I believe it has been proven that in some cases truly randomized or
non-deterministic automation are more efficient than deterministic. (I
don't have my theory books beside me in Israel.)
But I am not sure that the sort of nondeterminism we are talking about
here is as powerful as the nondeterminism in a non-deterministic
finite state automaton.
Sigh. The so-called nondeterministic automata are nothing of the
sort. They are completely deterministic and are equivalent to
what the computer scientists call deterministic ones with a single
extra primitive:
Apply function F to operand sets A(1...N) and return TRUE if
any of F(A[i])) return TRUE, but in time max(time(F(A[i])))
not sum(time(F(A[i]))).
|
Yes, which is why with sufficient parallelism (N-way in this case), you
should be able to evaluate the F(A[i]) in parallel and then
(non-deterministically) bug out if any of them return TRUE, yielding the
same efficiency as a non-deterministic automata. Yes? I don't have my
theory books with me either, and this isn't a tangent I will be staying
awake for. :-)
-Dave |
|
| Back to top |
|
|
David C. DiNucci
Guest
|
| Posted:
Thu Sep 22, 2005 2:35 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Jan Vorbrüggen wrote:
| Quote: | ... a large fraction of the
benefit of formal methods can be obtained by writing a formal
specification,
and that a large part of the benefit of doing _that_ is in forcing the
customer/user/... to actually think about what she wants to have done,
involving all concerned, and to commit to that in written form.
|
This is a large part of why I made the "P" in ScalPL stand for
"Planning" rather than "Programming", and why I refashioned the
documentation (from Software Cabling) to use nomenclature that a
customer (as well as a programmer) might relate to. A ScalPL strategy
can be regarded as a formal spec which can evolve into a program. BUT,
I've heard enough debates over the years as to whether an executable (or
even effective) expression can really be called a spec, or whether there
should even be a separate specification phase in software development,
that I've tried to avoid using the term "executable specification" for
ScalPL plans. I've heard the Haskell folks use the term, though, for
similar constructs.
-Dave |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Thu Sep 22, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Nick Maclaren wrote:
| Quote: | In article <3oq3n6F6v9qrU2@individual.net>,
=?ISO-8859-1?Q?Jan_Vorbr=FCggen?= <jvorbrueggen-not@mediasec.de> wrote:
A gentleman who could see further through a brick wall than most, as
the saying goes.
Perhaps so - but it was all destructive criticism, no suggestions of what
to try in its place.
Not at all. When people are making a complete pig's ear of something,
ANY solution involves starting again from scratch, and they are
stubbornly refusing to admit it, apparently constructive criticism
is destructive and apparently destructive criticism is constructive.
Exactly WHAT is destructive about saying "Look, you have got the
basic principles of your approach wrong. Don't attempt to fix up the
mess. Scrap it, go back to basics, and rethink your objectives."
I have been damned for saying that about C and POSIX, but exactly
HOW would YOU attempt to design an aircraft for carrying passengers
across the Atlantic using a coal-fired steam engine? That is not a
perverse example, incidentally - it was attempted in all seriousness.
Regards,
Nick Maclaren.
|
Easy, I would use a dirigible. Without having to waste fuel on staying
in the air, a coal fired (high energy per pound) steam engine would work
adequately, would be my take. Today's jet aircraft spend much energy
just staying in the air.
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Sep 22, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <peyphdcdfigd.fsf@pxpl2829.amr.corp.intel.com>,
Andy Glew <andy.glew@intel.com> writes:
|>
|> I'll admit to being weak on the terminology, but
|>
|> (0) if the official definition of NDFA is what Nick is talking about
|> (0.1) it is not what I wish to talk about
|> (0.2) it is deterministic, in both results and time
|> (0.3) it should execute well in parallel.
|> (0.4) it admits early out algorithms.
With reservations on 0.2 and 0.3, I agree on all counts.
|> (1) But that's not what I want to talk about.
|>
|> Unless my memory has totally failed me, there are truly
|> non-deterministic or randomized algorithms.
There are, indeed. Many of them, and many classes of them. What
is more is that they have been used and analysed before computer
science ever became a subject.
|> In Dijkstra's notation
|>
|> DO
|> :: guard1 -> s1;
|> :: guard2 -> s2;
|> :: guard3 -> s3;
|> OD
|>
|> where each statement is executed only if it's guard is true, but if
|> more than one guard is true, which is chosen to execute is random.
|> Not what Nick wrote.
Yes. That is one form, of many. [1].
|> And, again, unless my memory has failed me, there are cases where such
|> randomized algorithms are proven more efficient (probaibilistically
|> more efficient) than any determinstic algorithm. E.g. in time O(nlgn)
|> find a number that is 99% likely to be the best number, where the
|> optimal is significantly worse, maybe O(exp N).
Actually, it's not quite that simple.
|> I am sorry, but I do not recall the "official" name for this set of
|> randomized algorithms.
Non-deterministic algorithms. Seriously. Modern computer scientists
call them probabilistic, which is ANOTHER gross abuse of established
terminology!
|> (3) But, if you allow me to introduce my own names:
|>
|> If D.1 is the set of algorithms that run on a determistic uniprocessor
|> D.D.n is the set of algorithms that ruin on a fully deterministic multiprocessor,
|> such as Myrias
|> D.ND.n is the set of algorithms that run on a "deterministic chaos" multiprocessor
|> R.1 is the set of algorithms that run on a truly randomized uniprocessor
|> R.n is the set of algorithms that run on a truly randomized multiprocessor
|>
|> I am interested in whether there are any problems that live in the difference.
Me too - and I have been for a long time.
|> I.e. if A\P is the complexity of an algorithm to solve problem P that lives
|> in one of the sets above
|>
|> Then I am interested in what P have
|> D.ND.n\P / D.D.n\P = constant, O(n), etc.
|>
|> I suspect that it is a constant.
Here is a VERY brief summary of what is known, but I really must
get back to dealing with the local bureaucracy, which is diverting
me from real work.
There are three main aspects: whether the abstract machine
includes a source of true random bits (what many computer
scientists misleadingly call a random oracle), whether the
problem is phrased in non-deterministic terms, and whether the
stopping rule may be non-deterministic. A problem may be
non-deterministic in all 7 combinations of these!
Your example [1] is of the first class. It is known that the
provision of a random bit sequence makes no difference if the
problem is a deterministic language recognition one, and many
people (including me) believe that is almost certainly the case
for all deterministic problems with deterministic stopping rules.
[ I could go on at some length here, but let's not. ]
Examples of non-deterministic problems are "Solve this equation
to within accuracy X" and "Minimise this function to within 10%
of optimal".
Examples of non-deterministic stopping rules are "Tell me if this
assertion is true with type 1 and 2 errors of below P1 and P2"
or (more concretely) "Tell me if this number is prime with a
probability of error of below 1.0e-24".
It is easy to produce realistic examples of where problems can
be solved non-deterministically in the latter two senses with
a MUCH lower complexity (often O(n) versus O(exp(n))) than they
can be solved deterministically. This has been well-established
both theoretically and practically for well over half a century;
i.e. long before computer science was invented as a term.
Most of such analysis was and is done by statisticians and the
people in other fields who did and do serious statistics. Most
computer science results in this area are unmitigated rubbish.
A few are not, but they are hard to extract from the junk.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Andy Glew
Guest
|
| Posted:
Thu Sep 22, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
| Quote: | But I am not sure that the sort of nondeterminism we are talking about
here is as powerful as the nondeterminism in a non-deterministic
finite state automaton.
Sigh. The so-called nondeterministic automata are nothing of the
sort. They are completely deterministic and are equivalent to
what the computer scientists call deterministic ones with a single
extra primitive:
Apply function F to operand sets A(1...N) and return TRUE if
any of F(A[i])) return TRUE, but in time max(time(F(A[i])))
not sum(time(F(A[i]))).
Yes, which is why with sufficient parallelism (N-way in this case),
you should be able to evaluate the F(A[i]) in parallel and then
(non-deterministically) bug out if any of them return TRUE, yielding
the same efficiency as a non-deterministic automata. Yes? I don't
have my theory books with me either, and this isn't a tangent I will
be staying awake for. :-)
|
I'll admit to being weak on the terminology, but
(0) if the official definition of NDFA is what Nick is talking about
(0.1) it is not what I wish to talk about
(0.2) it is deterministic, in both results and time
(0.3) it should execute well in parallel.
(0.4) it admits early out algorithms.
(1) But that's not what I want to talk about.
Unless my memory has totally failed me, there are truly
non-deterministic or randomized algorithms.
In Dijkstra's notation
DO
:: guard1 -> s1;
:: guard2 -> s2;
:: guard3 -> s3;
OD
where each statement is executed only if it's guard is true, but if
more than one guard is true, which is chosen to execute is random.
Not what Nick wrote.
And, again, unless my memory has failed me, there are cases where such
randomized algorithms are proven more efficient (probaibilistically
more efficient) than any determinstic algorithm. E.g. in time O(nlgn)
find a number that is 99% likely to be the best number, where the
optimal is significantly worse, maybe O(exp N).
I am sorry, but I do not recall the "official" name for this set of
randomized algorithms.
(3) But, if you allow me to introduce my own names:
If D.1 is the set of algorithms that run on a determistic uniprocessor
D.D.n is the set of algorithms that ruin on a fully deterministic multiprocessor,
such as Myrias
D.ND.n is the set of algorithms that run on a "deterministic chaos" multiprocessor
R.1 is the set of algorithms that run on a truly randomized uniprocessor
R.n is the set of algorithms that run on a truly randomized multiprocessor
I am interested in whether there are any problems that live in the difference.
I.e. if A\P is the complexity of an algorithm to solve problem P that lives
in one of the sets above
Then I am interested in what P have
D.ND.n\P / D.D.n\P = constant, O(n), etc.
I suspect that it is a constant. |
|
| Back to top |
|
|
Guest
|
| Posted:
Thu Sep 22, 2005 9:53 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Del Cecchi wrote:
| Quote: | Nick Maclaren wrote:
snip
I have been damned for saying that about C and POSIX, but exactly
HOW would YOU attempt to design an aircraft for carrying passengers
across the Atlantic using a coal-fired steam engine? That is not a
perverse example, incidentally - it was attempted in all seriousness.
Regards,
Nick Maclaren.
Easy, I would use a dirigible. Without having to waste fuel on staying
in the air, a coal fired (high energy per pound) steam engine would work
adequately, would be my take. Today's jet aircraft spend much energy
just staying in the air.
|
While a coal fired dirigible might actually be able to make the trip:
1. I believe a gasoline or diesel engine can get a higher energy per
pound
2. The cinders from a coal fired engine pose a fire hazard given how
friable the outer skin of an airship typically was and the use of
hydrogen for boyancy in almost all designs due to the limited
avialability of large quantities of helium.
Note that one of the many problems with the British R101 airship was
its reliance on heavy dieseel engines. |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Sep 22, 2005 10:04 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <3pg1bnFa4jspU1@individual.net>,
Del Cecchi <cecchinospam@us.ibm.com> wrote:
| Quote: |
Exactly WHAT is destructive about saying "Look, you have got the
basic principles of your approach wrong. Don't attempt to fix up the
mess. Scrap it, go back to basics, and rethink your objectives."
I have been damned for saying that about C and POSIX, but exactly
HOW would YOU attempt to design an aircraft for carrying passengers
across the Atlantic using a coal-fired steam engine? That is not a
perverse example, incidentally - it was attempted in all seriousness.
Easy, I would use a dirigible. Without having to waste fuel on staying
in the air, a coal fired (high energy per pound) steam engine would work
adequately, would be my take. Today's jet aircraft spend much energy
just staying in the air.
|
Right. That is an example of where you could reach a viable solution
by abandoning the infeasible approach and rethinking the design. As
in that case, there is often a solution that involves going back only
half way. As Bill Clodius says, that may still leave you with an
unsatisfactory solution, and it may be better not to go back just
enough to find a viable solution, but right back to the start.
Whichever solution you like, they are good examples of the benefits
of my apparently negative advice!
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Thu Sep 22, 2005 11:18 pm Post subject:
Re: Not enough parallelism in programming |
|
|
wclodius@lanl.gov wrote:
| Quote: | Del Cecchi wrote:
Nick Maclaren wrote:
snip
I have been damned for saying that about C and POSIX, but exactly
HOW would YOU attempt to design an aircraft for carrying passengers
across the Atlantic using a coal-fired steam engine? That is not a
perverse example, incidentally - it was attempted in all seriousness.
Regards,
Nick Maclaren.
Easy, I would use a dirigible. Without having to waste fuel on staying
in the air, a coal fired (high energy per pound) steam engine would work
adequately, would be my take. Today's jet aircraft spend much energy
just staying in the air.
While a coal fired dirigible might actually be able to make the trip:
1. I believe a gasoline or diesel engine can get a higher energy per
pound
2. The cinders from a coal fired engine pose a fire hazard given how
friable the outer skin of an airship typically was and the use of
hydrogen for boyancy in almost all designs due to the limited
avialability of large quantities of helium.
Note that one of the many problems with the British R101 airship was
its reliance on heavy dieseel engines.
The question was how I would design a transatlantic coal/steam passenger |
airship. Dirigible was the obvious solution. Coal has an energy per
pound only 20 percent less than diesel fuel which I believe to be
similar to jet fuel, so it might be possible to build a gas turbine that
burns powdered coal but that was not the question.
And since I would use helium which is now in abundant supply, there
wouldn't be a fire hazard.
I might even cover the top surface with thin film solar cells to provide
extra power for at least part of the trip. :-)
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Fri Sep 23, 2005 4:15 pm Post subject:
Schematics and VLSI Re: Not enough parallelism in programmin |
|
|
JJ wrote:
| Quote: | Andy Glew wrote:
Elaborating on my previous posts: I want somebody to define a parallel
or concurrent language where the meaning of not only the simple
statements such as are defined:
I will come back to this later after the cpa2005 conference.
Of the 25 or so odd papers I and another paper from U of CA propose a
Verilog + C hybrid, I want to see where these researchers are going
before I say anything. Most folks here won't know what Verilog or RTL
is all about or will take the time the time to look but VHDL might be
better known. Same is somewhat true for occam but a few here do know
that but occam is treated as a dead language dragged up by tired old
ranters like me and Rupert.
Now combine the set of people that can talk of Verilog and occam, you
are down to 2 I know of and others who never come here. Switch to VHDL
I drop out and others might drop in.
The real question is what is an object.
Many years ago I had the pleasure and time to write a full custom VLSI
layout editor for the Mac, I wanted this to do VLSI layout ofcourse, I
couldn't afford the Calma type stuff. I learned all about Event driven
programming, and later C++ OO came along. I am so glad I did this on
the Mac before OO came otherwise I suspect the whole thing might have
been a monster.
This full blown VLSI editer (used on a no of real fabbed chips) took up
a whopping 37KBytes. Today if I fire up an MFC or other framework and
auto build a template GUI program with zero content, I start at 400K
for bloody nothing.
One can see why SW is in a mess when nothing is 10x bigger than a
finnished product. Even interpreted on Windows under Basilisk, it rocks
way more than the original 68K it was written for.
Later I learnt Verilog, I was a bit sad to see the schematic appoach to
VLSI go away, but the synthesis justifies it, otherwise I might still
be hacking manual shift driven EDA SW.
|
The schematic approach is still alive and well in various core and
processor design projects. And these cores would have been full chips
only a few years ago. Cadence still sells schematic capture and layout,
although they change the names every couple years.
| Quote: |
Recently for this Transputer project that is supposed to run a hybrid
Verilog C occam subset I was thinking about how a GUI OS like say BeOS
would be written for it. Well any respectable SW engineer would say C++
right away and indeed BeOS API is a nice looking C++ kit while MFC is a
stinkin...
I actually think now that if GUIs use real world hardware models of
widgets like buttons (1,0), sliders (1.0--0.0), and a myriad of other
widget types, I can see the natural way to do that would be with
Verilog for all the event driven stuff and C for the lower level stuff.
module menuBar(in mouseUpDOwn, in mouseXY, out startPaneDownTrack..)
always @(mouseUpDOwn) {
// start
}
I am still getting my arms around this one, clearly C and occam can fit
in here too. Some will suggest occam !? PAR ALT framework copuld build
a GUI too, but GUIs are all about
..
I can see a set of modules instanced in a hierarchy as any chip would
be, but the signals connecting them up are as live as one can get, they
are real event driven wires carrying 1,0,z,x values or possibly objects
too. Verilog doesn't have the object idea just raw wire types.
The natural way to draw the GUI app would be with something that looks
remarkably like a VLSI editor too, attaching (instancing widgets) to
parent cells (panes) and so on. What needs to be added to the VLSI
editer are more object types besides boxes, polygons, such as pixmaps
and live signals.
I am reminded of Electric tools that had live VLSI editing, ie the
signals could be active while working with it.
The funny thing is that due to synthesis all research in VLSI graphics
except P/R is dead, no more schematics. While the SW crowd keeps
reiventing schematics with a sense of liveness.
Now put a bunch of people with vastly different backgrounds like that
in a company and crazy things pop out like occam and a Transputer.
talk later on specific points you make.
johnjakson at usa dot ..
transputer2 at yahoo
|
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
| Back to top |
|
|
JJ
Guest
|
| Posted:
Sat Sep 24, 2005 12:15 am Post subject:
Re: Schematics and VLSI Re: Not enough parallelism in progra |
|
|
Del Cecchi wrote:
snipping to schematics
| Quote: | Later I learnt Verilog, I was a bit sad to see the schematic appoach to
VLSI go away, but the synthesis justifies it, otherwise I might still
be hacking manual shift driven EDA SW.
The schematic approach is still alive and well in various core and
processor design projects. And these cores would have been full chips
only a few years ago. Cadence still sells schematic capture and layout,
although they change the names every couple years.
|
Ofcourse. I suspect that open market synthesis probably limits out to
1GHz clock rates at best and then only for std cell. Anything above
will be schematic and heavy on the manpower with inhouse special
purpose synthesis tools for data or control paths.
The last schematics I really enjoyed were VLSI/Compass, and perhaps
later Cadence whatever it was called. I suppose Cell Ensemble hasn't
changed much either.
These days in FPGA land, no useful schematic entry available esp for
input.
johnjakson at usa dot ..
transputer2 at yahoo |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Sat Sep 24, 2005 5:39 am Post subject:
Re: Schematics and VLSI Re: Not enough parallelism in progra |
|
|
"JJ" <johnjakson@gmail.com> wrote in message
news:1127512816.915553.149110@f14g2000cwb.googlegroups.com...
| Quote: |
Del Cecchi wrote:
snipping to schematics
Later I learnt Verilog, I was a bit sad to see the schematic appoach
to
VLSI go away, but the synthesis justifies it, otherwise I might
still
be hacking manual shift driven EDA SW.
The schematic approach is still alive and well in various core and
processor design projects. And these cores would have been full chips
only a few years ago. Cadence still sells schematic capture and
layout,
although they change the names every couple years.
Ofcourse. I suspect that open market synthesis probably limits out to
1GHz clock rates at best and then only for std cell. Anything above
will be schematic and heavy on the manpower with inhouse special
purpose synthesis tools for data or control paths.
The last schematics I really enjoyed were VLSI/Compass, and perhaps
later Cadence whatever it was called. I suppose Cell Ensemble hasn't
changed much either.
These days in FPGA land, no useful schematic entry available esp for
input.
johnjakson at usa dot ..
transputer2 at yahoo
If you really want to, you can instantiate the netlist pretty directly in |
vhdl. It's not drawing pretty pictures but it works.
If you are doing FPGA work, I would think HDL and synthesis would be just
the ticket since the FPGA building blocks aren't the normal schematic
type constructs. Or would you propose some sort of transistor level like
design methodology for FPGA?
Del |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in