dual core and c

Discussion in 'C Programming' started by kerravon, Feb 29, 2008.

  1. kerravon

    kerravon Guest

    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.
    kerravon, Feb 29, 2008
    #1
    1. Advertising

  2. In article <>,
    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
    Walter Roberson, Feb 29, 2008
    #2
    1. Advertising

  3. 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...
    Antoninus Twink, Feb 29, 2008
    #3
  4. kerravon

    Eric Sosman Guest

    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>

    --
    Eric Sosman, Feb 29, 2008
    #4
  5. 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.
    Kenny McCormack, Feb 29, 2008
    #5
  6. kerravon

    Nelu Guest

    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...)
    Nelu, Feb 29, 2008
    #6
  7. kerravon

    Paul Hsieh Guest

    On Feb 29, 7:13 am, 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,


    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/
    Paul Hsieh, Feb 29, 2008
    #7
  8. In article <>,
    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
    Walter Roberson, Feb 29, 2008
    #8
  9. kerravon

    user923005 Guest

    On Feb 29, 7:13 am, 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?  


    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.programming.threads/topics?lnk=sg
    user923005, Feb 29, 2008
    #9
  10. kerravon

    CBFalconer Guest

    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
    CBFalconer, Feb 29, 2008
    #10
  11. "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.


    That's only true if your compiler has no multi-threading
    capability, or if it does but you don't use it. To get
    multi-threading going, you have to have a compiler that
    supports it, and you have to actually use its multi-threaded
    capabilities by starting tasks in their own threads.
    A single-threaded program is unlikely to run much faster
    just because you run it on a multi-core CPU.

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


    As I understand it, a "core" is almost an entire CPU, with
    it's own ALU, registers, etc; as for exactly what is shared
    and what is separate, you'd have to RTFM* for your CPU.

    > 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?


    No, generally a multi-threading compiler will run one thread
    per core. Each thread is defined by an entry function, which
    usually consists of a for loop which loops until either the
    thread is no-longer needed or the application exits. Any
    functions called by the thread function will also be a part
    of that thread and run on that thread's core.

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


    The C language itself neither supports nor thwarts parallel
    processing. That's a function of your compiler. RTFM* for
    your compiler.

    My compiler at work (National Instruments LabWindows/CVI) *does*
    support parallel processing. It comes with a multi-threading
    library, which I make heavy use of, because the program I'm
    working on needs to be doing multiple things in real-time, and
    it is not acceptable for one task to have to stop and wait for
    another to complete. So I put the different tasks in different
    threads.

    A multi-threaded compiler such as LabWindows/CVI will first look
    for multiple cores to run threads in, and if it finds them, it
    will attempt to distribute one thread per core.

    If it runs out of cores (or if there is only one), it then shares
    multiple threads per core by time-sharing (jumping execution
    rapidly back and forth between two threads on the same core).

    For example, here's how one program I'm working on launches
    a couple of new threads:

    // Start communications thread:
    CmtScheduleThreadPoolFunction
    (
    DEFAULT_THREAD_POOL_HANDLE, // thread pool handle
    CommThread, // thread function
    (void*)0,
    &thrdCommunications // thread id
    );

    // Start background thread:
    CmtScheduleThreadPoolFunction
    (
    DEFAULT_THREAD_POOL_HANDLE, // thread pool handle
    BackgroundThread, // thread function
    (void*)0,
    &thrdBackground // thread id
    );

    If separate CPU cores are available, those will run in
    separate cores; otherwise, they'll be time-shared on
    the same core.

    Multi-threaded programming does take some getting used to, though.
    You need to watch out for booboos such as thread A getting to a
    certain point then waiting for thread B to complete, with
    thread B also having a point where it stops and waits for
    thread A to complete. Ooops! Deadlock.

    Also, you need to be aware that multiple thread can access
    the same global variables. Say thread A stores "57" in
    global variable "int argle" and leaves it there for a while
    without changing it. Later, thread A comes back and reads
    argle and finds that its value is now "87375629". What
    happened??? I'll tell you what happened! Thread B wrote
    to it, overwriting what thread A had written to it. Gotta
    watch out for that. Only use global variables for things
    which absolutely MUST be global, especially when doing
    multi-threaded programming.


    Footnotes:
    *RTFM: "Read the Fine Manual". (Or substitute another word for
    "fine" if that suits your fancy better.)

    --
    Cheers,
    Robbie Hatley
    lonewolf aatt well dott com
    www dott well dott com slant user slant lonewolf slant
    Robbie Hatley, Mar 1, 2008
    #11
  12. On Fri, 29 Feb 2008 18:33:18 UTC, Paul Hsieh <>
    wrote:

    > On Feb 29, 7:13 am, 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,

    >
    > C, according to the standard, is not a language that is up to the task
    > of doing anything about parallel or multithreaded programming.


    This is not true. The standard does neither allow or forbid an
    compiler to generate code that uses multiple CPUs, multiple pipelines
    in parallel. So it lefts the job to paralise code for multiple CPUs
    only to the compiler.

    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.


    The standard lets any freedom to an implementation if it supports
    multithreading and/or any other kind of parallelism of handling
    multiple CPUs. Only the implementation knows if there are multiple
    CPUs avaiilable, if the multiple CPUs can work parallel in a single
    thread, if it can assign only one or more CPUs to one or more
    processes or threads in parallel. There is nothing in the standard
    that allows or forbids that.

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


    Not true. Read the standard carefully and you'll see that it does
    explicity allows to parallise instructions. The only requirement on
    statements is that they have to be complete done on each sequence
    point. It allows even to split off multiple sequences of statements in
    parallel.

    > > [...] 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.


    No, even a single instance of zip or something like a webserver (even
    a single connection) can use multiple CPUs in parallel. Its left only
    to the implementation to use these abilities when they exist.

    > > 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.


    No, many. It is up to the implementation to coordinate the CPUs in a
    manner that at a sequence point a given statement is complete done or
    at least to guarantee that it behaves exactly as if it were even as it
    is not.

    > > [...] 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.)


    Not true.

    > 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.


    Yes, exactly.

    > > 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.


    No, it depends only on the implementation. When the implementation can
    split a a single instruction sequence off to multiple cores in
    oarallel it can do that solong the visible result is not different
    from a strict sequential one.

    > 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.
    >



    --
    Tschau/Bye
    Herbert

    Visit http://www.ecomstation.de the home of german eComStation
    eComStation 1.2R Deutsch ist da!
    Herbert Rosenau, Mar 2, 2008
    #12
  13. kerravon

    santosh Guest

    Herbert Rosenau wrote:

    > On Fri, 29 Feb 2008 18:33:18 UTC, Paul Hsieh <>
    > wrote:
    >
    >> On Feb 29, 7:13 am, 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,

    >>
    >> C, according to the standard, is not a language that is up to the
    >> task of doing anything about parallel or multithreaded programming.

    >
    > This is not true. The standard does neither allow or forbid an
    > compiler to generate code that uses multiple CPUs, multiple pipelines
    > in parallel. So it lefts the job to paralise code for multiple CPUs
    > only to the compiler.


    I think that Paul means that C does not have any built in constructs for
    parallel programming. Neither does it have any standardised library
    facilities for this. That's why he said "C, according to the
    standard, ...".

    <snip>

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

    >
    > Not true. Read the standard carefully and you'll see that it does
    > explicity allows to parallise instructions. The only requirement on
    > statements is that they have to be complete done on each sequence
    > point. It allows even to split off multiple sequences of statements in
    > parallel.


    He is talking about parallelism above the instruction level.

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

    >
    > No, even a single instance of zip or something like a webserver (even
    > a single connection) can use multiple CPUs in parallel. Its left only
    > to the implementation to use these abilities when they exist.


    Yes, but this is rarely done without explicitly using implementation
    specific constructs for threading.

    <snip>
    santosh, Mar 2, 2008
    #13
  14. "kerravon" <> wrote in message
    news:...
    > 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.


    Your not going to experience any speedup wrt concurrency and scalability
    unless the thread synchronization scheme that you are using is well
    engineered. For instance, you have to pad data-structures up to a L2
    cacheline size and then align then on l2cache boundary's. You should
    minimize the use of membars and interlocked RMW instructions (e.g., try and
    avoid the LOCK prefix on x86m, and the membar instruction on SPARC). Try and
    use cache friendly algorithms in creative ways (e.g., distributed
    ref-counting, RCU, ect...)...

    As for single-threaded applications, well they should perform just as good
    as they did before. Maybe even a little bit worse. Think of a chip with many
    very many cores which run under a low clock speed such that a single-thread
    program could end up running on a core that is most likely slower than a
    single-chip/core system...
    Chris Thomasson, Mar 3, 2008
    #14
  15. kerravon

    Paul Hsieh Guest

    On Feb 29, 10:49 am, -cnrc.gc.ca (Walter Roberson)
    wrote:
    > In article <>,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.


    Oh. I had no idea. I only know it from the base theoretical ideas
    behind it and just assumed that the whole thing was always self-
    dependent on the entire state before any emit point. Learn a new
    thing every day. Cheers.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    Paul Hsieh, Mar 4, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andy
    Replies:
    5
    Views:
    2,814
  2. malv

    Dual Core outlook

    malv, Feb 7, 2006, in forum: Python
    Replies:
    6
    Views:
    364
  3. robert
    Replies:
    2
    Views:
    438
  4. Simon Wittber

    Help me use my Dual Core CPU!

    Simon Wittber, Sep 12, 2006, in forum: Python
    Replies:
    23
    Views:
    740
    mystilleef
    Sep 18, 2006
  5. robert
    Replies:
    5
    Views:
    320
    Robert Kern
    Oct 2, 2006
Loading...

Share This Page