«

Assuming I am running a C program that is doing some cpu-intensive
work
such as zip -9, I can understand:

If I have 8 CPUs, then it will make no difference at all to the zip
program,
it will only run on one of the CPUs, although this does allow me to
run 8
separate zips simultaneously, which would be cool on a large site.

But what I don't understand is the concept of a "core", as in "dual
core".
What implications does that have for a C program like zip? Does it
have the ability to look at the instructions ahead of time and
pipeline
them or something? Pipelining is something that has been around for
a long time. Did someone just get the bright idea to call it dual
core
instead or what?

Assume the zip in question is written in C89, no fancy parallelism -
at
least not inherent in the language itself.

Thanks. Paul.

In article <fc3a1730-b0c1-47d7-b592->,
kerravon <> wrote:
>Assuming I am running a C program that is doing some cpu-intensive
>work
>such as zip -9, I can understand:

>If I have 8 CPUs, then it will make no difference at all to the zip
>program,
>it will only run on one of the CPUs,

Quite possibly true that it would only run on one of the CPUs
(or cores), but you might be interested to know that several
standard compression algorithms turn out to be ameniable to
"divide and conquer" strategies using multiple CPUs or multiple
cores. For some of the algorithms, there would be no loss of
compression ability at all (e.g., there are parallel sorting
algorithms for the block sort phase); for others of the algorithms,
(including standard LZW type of algorithms), there would be a minor
loss of compression efficiency but a fair reduction in CPU time.
--
"The slogans of an inadequate criticism peddle ideas to fashion"
-- Walter Benjamin

On 29 Feb 2008 at 15:13, kerravon wrote:
> Assuming I am running a C program that is doing some cpu-intensive
> work
> such as zip -9, I can understand:
>
> If I have 8 CPUs, then it will make no difference at all to the zip
> program,
> it will only run on one of the CPUs, although this does allow me to
> run 8
> separate zips simultaneously, which would be cool on a large site.
>
> But what I don't understand is the concept of a "core", as in "dual
> core".
> What implications does that have for a C program like zip? Does it
> have the ability to look at the instructions ahead of time and
> pipeline
> them or something? Pipelining is something that has been around for
> a long time. Did someone just get the bright idea to call it dual
> core
> instead or what?

And HeathField's attack dogs are unleashed in 3... 2... 1...

kerravon wrote:
> Assuming I am running a C program that is doing some cpu-intensive
> work
> such as zip -9, I can understand:
>
> If I have 8 CPUs, then it will make no difference at all to the zip
> program,
> it will only run on one of the CPUs, although this does allow me to
> run 8
> separate zips simultaneously, which would be cool on a large site.
>
> But what I don't understand is the concept of a "core", as in "dual
> core".

<off-topic>

What's usually meant is that a "core" is most of a CPU,
so a "dual-core" processor has two CPUs on one chip, an
eight-core processor has eight, and so on. It's not quite
as hard-and-fast as that, because the chip usually has some
components that are shared by all the cores but that would
be per-CPU resources in a traditional design: Caches, memory
controllers, I/O ports, and so on. But to some fuzzy level
of approximation, a core is a CPU.

</off-topic>

> What implications does that have for a C program like zip? Does it
> have the ability to look at the instructions ahead of time and
> pipeline
> them or something? Pipelining is something that has been around for
> a long time. Did someone just get the bright idea to call it dual
> core
> instead or what?

<off-topic>

This is a question for a computer architecture forum,
not a question about a programming language.

</off-topic>

> Assume the zip in question is written in C89, no fancy parallelism -
> at
> least not inherent in the language itself.

<ON-topic>

The C language is defined in terms of an abstract machine
whose operations are almost entirely sequential. ("Almost"
because there are a few grudging nods toward asynchronous
activities -- signals, some uses of `volatile' -- and because
there's some leeway between "sequence points.") Thus, the C
language itself is almost entirely sequential; there's no
built-in way to express parallelism.

However, implementations of C are not required to model
the abstract machine in every detail. A principle called
the "as-if rule" allows an actual C implementation to play
all manner of optimization games, provided the ultimate outcome
is "as if" the abstract machine had performed the computation.
So if a compiler can detect opportunities for parallelism in a
C program, it's free to exploit those opportunities if it can.
But the C language itself gives you no way to control this --
indeed, by the way "as if" works, it gives you no way to
detect that something has been parallelized.

</ON-topic>

--

In article <>,
Antoninus Twink <> wrote:
....
>> But what I don't understand is the concept of a "core", as in "dual
>> core". What implications does that have for a C program like zip?
>> Does it have the ability to look at the instructions ahead of time
>> and pipeline them or something? Pipelining is something that has
>> been around for a long time. Did someone just get the bright idea to
>> call it dual core instead or what?
>
>And HeathField's attack dogs are unleashed in 3... 2... 1...
>

Yes. I was quite amazed to see that Roberson managed to post a response
in this thread - that wasn't the usual:

Off topic. Not portable. Cant discuss it here. Blah, blah, blah.

nonsense. He must be slipping. Clique membership possibly in doubt.

On Fri, 29 Feb 2008 15:58:55 +0000, Kenny McCormack wrote:

> In article <>, Antoninus Twink
> <> wrote: ...
<snip>
>>And HeathField's attack dogs are unleashed in 3... 2... 1...
>>
>>
> Yes. I was quite amazed to see that Roberson managed to post a response
> in this thread - that wasn't the usual:
>
> Off topic. Not portable. Cant discuss it here. Blah, blah, blah.
>
> nonsense. He must be slipping. Clique membership possibly in doubt.

I was expecting to see you all grown up, maybe posting something useful
and on topic every once in a while... Oh well, I see that, at least, you
have a friend to talk to.




--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

On Feb 29, 7:13*am, kerravon <kerra...@w3.to> wrote:
> Assuming I am running a C program that is doing some cpu-intensive
> work such as zip -9, I can understand:
>
> If I have 8 CPUs, then it will make no difference at all to the zip
> program, it will only run on one of the CPUs,

C, according to the standard, is not a language that is up to the task
of doing anything about parallel or multithreaded programming. There
has been some interesting research into compilers that perform
automatic conversion of some loops to multithreaded object code, but
these are silly research things that only apply to the most obvious
cases, which LZ compression is *not* an example of.

With pretty much any compiler environment you will get exactly one
core/CPU/thread usage here no matter what.

> [...] although this does allow me to
> run 8 separate zips simultaneously, which would be cool on a large
> site.

If you want to run several instances of zip on something like a
webserver (one per connection), then yes that's fine.

> But what I don't understand is the concept of a "core", as in "dual
> core".

It is essentially the same as dual processor. The difference is more
pronounced on AMD CPUs because they use a shared core-centric memory
controller (this means that memory shared between two different cores
is much faster than between two different processors.) But this is
*way* off topic with respect to the C language specification.

> What implications does that have for a C program like zip?

None.

> [...]*Does it have the ability to look at the instructions ahead of
> time and pipeline them or something? *

That's not what dual core means. The "out of order execution" of
these CPUs is what it allows it to do that (and all the modern stuff
does that on a per CPU basis.)

> [...] Pipelining is something that has been around for
> a long time.

It has. It has nothing to do with dual process or dual core
(excepting in that the concept is to offer more computational
resources.)

> [...]*Did someone just get the bright idea to call it dual
> core instead or what?

Specifically, dual core refers to the specific activity of glueing two
CPU cores into a single microprocessor. Its a chip design thing.
From software's point of view, it should be viewed as if there are
multiple processors in the system.

> Assume the zip in question is written in C89, no fancy parallelism -
> at least not inherent in the language itself.

With such a program, just running one instance of it straight, on
pretty much any contemporary compiler, it means your 8-core machine
will run at one eighth capacity.

To get more performance, you will need 1) To paralellize the algorithm
(its not obvious that can even be done for zip, which is LZ based
compression/decompression) and 2) Use a programming language/compiler
that supports parallelism. Java supports parallelism out of the box,
but many C compilers also support extensions for parallelism support.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

In article <4f2cd564-c9e1-412c-8c01->,
Paul Hsieh <> wrote:

>To get more performance, you will need 1) To paralellize the algorithm
>(its not obvious that can even be done for zip, which is LZ based
>compression/decompression)

[OT]

It turns out that parallelizing LZ compression or decompression is
not difficult. The LZ algorithms reset the code dictionary from
time to time, in order to adapt to changes in the data. This is
done by emitting a "flush" token and flushing out all pending
encodings, starting the encoded data again on a byte boundary.
This is the same token that is used at end of file. (A consequence
of this is that you can simply concatenate together several LZ
encoded files and the decompression of the result would be the same
as if the original files had been appended together before compression.)
Different LZ implementations use different strategies for deciding
-when- to flush, but this flushing behaviour is a fairly consistant
property of the family of algorithms.

Thus, in order to parallelize LZ compression, all that has to be
done is to split the file up into pieces, do an LZ compression
independantly on the pieces, and concatenate the encoded pieces
together to form the output. There may be a small loss of encoding
efficiency in doing so (corresponding to the extra output from
flushing at each boundary and rebuilding the data dictionary); on
the other hand, it could also happen that the result was smaller than
it would otherwise be, if it happened that the boundaries chosen
lay near places where the statistical properties changed noticably
and the LZ algorithm would have otherwise delayed resetting the
dictionary until it was more sure that a dictionary reset was
warranted.

For parallel decompression, you have to find the reset tokens
in the encoded data, split the data streams there, and decode
each chunk, concatenating the results.
--
"We may gather out of history a policy, by the comparison and
application of other men's forepassed miseries with our own like
errors and ill deservings." -- Sir Walter Raleigh

On Feb 29, 7:13*am, kerravon <kerra...@w3.to> wrote:
> Assuming I am running a C program that is doing some cpu-intensive
> work
> such as zip -9, I can understand:
>
> If I have 8 CPUs, then it will make no difference at all to the zip
> program,
> it will only run on one of the CPUs, although this does allow me to
> run 8
> separate zips simultaneously, which would be cool on a large site.
>
> But what I don't understand is the concept of a "core", as in "dual
> core".
> What implications does that have for a C program like zip? *

In order for a C program to take advantage of multiple threads of
execution, it will require a non-portable call to create threads or
processes or to use an interface like MPI.
See, for instance:
http://www.cs.cf.ac.uk/Dave/C/node29.html
http://www.mhpcc.edu/training/workshop/mpi/MAIN.html

> Does it
> have the ability to look at the instructions ahead of time and
> pipeline
> them or something? *

Usually, the programmer has to take some kind of action, but some
compilers can spit out parallel tasks to some degree.

> Pipelining is something that has been around for
> a long time. *Did someone just get the bright idea to call it dual
> core
> instead or what?

Pipelining does not rely upon more than one CPU core. You can have
multiple pipes executing simultaneously on a machine with a single CPU
with only one processor on the CPU.

> Assume the zip in question is written in C89, no fancy parallelism -
> at
> least not inherent in the language itself.

Yes. The Cilk langugage is a modification of C that tries to make
threading more transparent:
http://supertech.csail.mit.edu/cilk/

If you want to actually implement something that works in parallel,
probably pthreads is the closest thing to a ubiquitous interface in
C. It works on Windows and many Unix variants.
http://en.wikipedia.org/wiki/POSIX_Threads

If you are programming in a Unix or POSIX environment, you might try
news:comp.programming.threads:
http://groups.google.com/group/comp..../topics?lnk=sg

Walter Roberson wrote:
> Paul Hsieh <> wrote:
>
>> To get more performance, you will need 1) To paralellize the
>> algorithm (its not obvious that can even be done for zip, which
>> is LZ based compression/decompression)
>
> [OT]
>
> It turns out that parallelizing LZ compression or decompression is
> not difficult. The LZ algorithms reset the code dictionary from
> time to time, in order to adapt to changes in the data. This is
> done by emitting a "flush" token and flushing out all pending
> encodings, starting the encoded data again on a byte boundary.
> This is the same token that is used at end of file. (A consequence
> of this is that you can simply concatenate together several LZ
> encoded files and the decompression of the result would be the
> same as if the original files had been appended together before
> compression.) Different LZ implementations use different strategies
> for deciding -when- to flush, but this flushing behaviour is a
> fairly consistant property of the family of algorithms.

At least one of us is confused. IIRC LZ is the method used in zip,
and LZW is the earlier technique. LZW required periodic reset and
reformation of the compression table. LZ depends only on the
history over the past (limited size) block. Thus LZ continuously
adapts to the input data, and doesn't leave convenient
opportunities for breaks. I don't think LZW does either, because
the next break location will depend on performance during this
block.

I may well have the identifiers fouled, but not the basic
processes.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com