Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2016 > unrolled thread

Skybuck's Parallel Static Huffman Decoding Algorithm

Back to article view | Back to comp.compression

Contents

  Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 06:37 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-09-12 05:54 +0000
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:28 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm Dombo <dombo@disposable.invalid> - 2013-09-14 14:57 +0200
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm Willem <willem@turtle.stack.nl> - 2013-09-14 19:12 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Jasen Betts <jasen@xnet.co.nz> - 2013-09-12 13:31 +0000
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:30 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm BGB <cr88192@hotmail.com> - 2013-09-12 19:39 -0500
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Shaun" <stereobuff07@gmail.com> - 2013-09-19 04:26 -0500
          Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-22 03:25 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Thomas Richter <thor@math.tu-berlin.de> - 2013-09-21 10:09 +0200

#2016 — Skybuck's Parallel Static Huffman Decoding Algorithm

Hello,

Today/Tonight I had an idea how to fund my Algorithm skills ;) :)

It's always funny to see how some programmers believe that Huffman cannot be 
decoded in parallel.

I believe it is possible to decode (static) huffman in parallel.

However as I wrote in the past I want a million dollars for it ! ;)

Perhaps nobody is going to pay 1 million dollars all by him/herself so 
instead I am going to give crowd funding a try ! ;)

I just created a project for it and here you can find it and donate if you 
are curious:

http://igg.me/p/525568/x/4730405

Tomorrow I will also add a new project for my Cuda/Delphi Framework so that 
hopefully a million Delphi programmers can start using Cuda with ease ! ;)

The Cuda/Delphi framework is super real.

The algorithm is inside my head and in a draft so it will need further work 
and ofcourse implementations will be made ! ;)

Read the project description for more information about the algorithm ! ;)

Do tell everybody about it too ! ;)

Bye,
  Skybuck.

[toc] | [next] | [standalone]

#2017

In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:

(snip)
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
 
> It's always funny to see how some programmers believe that 
> Huffman cannot be decoded in parallel.

No, not impossible, but not so easy, either.
 
> I believe it is possible to decode (static) huffman in parallel.
 
> However as I wrote in the past I want a million dollars for it ! ;)
 
> Perhaps nobody is going to pay 1 million dollars all by him/herself so 
> instead I am going to give crowd funding a try ! ;)

The VAX instruction format was designed to efficiently use the
bits, in a way somewhat similar to the way Huffman does.
Instructions can have from one up to some high number of bytes,
maybe 16 or so. It is not easy to figure out how many, either.
That is one reason that VAX didn't last longer than it did.

In contrast, the S/360 (and successor) instruction length is
known from the first two bits of the opcode. Not quite as easy
as with only one length (most RISC) but pretty easy.

So, yes, if the length can be determined from a small number of
bits in the beginning, then it isn't hard to do in parallel.

IA32 is pretty CISCy, but not quite as bad as VAX. It takes some
pretty strange logic to decode it and generate RISC-like code
to actually execute, possibly out of order, and in parallel.

-- glen

[toc] | [prev] | [next] | [standalone]

#2019

Hmm interesting.

I didn't realize my invention could be used to decode instructions in 
parallel as well.

But that is indeed possible as well.

Even for variable size instructions, just like huffman codes.

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#2022

Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
>
> (snip)
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
>> It's always funny to see how some programmers believe that
>> Huffman cannot be decoded in parallel.
>
> No, not impossible, but not so easy, either.

It is possible and not that hard either, and in fact has been done many 
times before by many people (myself included). I'm inclined to believe 
that you'll only see pure serial Huffman decoding in classrooms.

[toc] | [prev] | [next] | [standalone]

#2023

Dombo wrote:
) Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
)> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
)>
)> (snip)
)>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
)>
)>> It's always funny to see how some programmers believe that
)>> Huffman cannot be decoded in parallel.
)>
)> No, not impossible, but not so easy, either.
)
) It is possible and not that hard either, and in fact has been done many 
) times before by many people (myself included). I'm inclined to believe 
) that you'll only see pure serial Huffman decoding in classrooms.

That depends on if you get to control the encoding side.

A small bit of extra work on the encoding side makes it easy to decode
chunks in parallel, otherwise you have several problems, such as the
impossibility to decide the position in the decoded stream without
decoding the previous stream, and the existence of encoded streams
where each position leads to a valid (but different) decoded stream,
only one of which is the correct one.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#2018

On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
> Hello,
>
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
> It's always funny to see how some programmers believe that Huffman cannot be 
> decoded in parallel.
>
> I believe it is possible to decode (static) huffman in parallel.
>
> However as I wrote in the past I want a million dollars for it ! ;)
>
> Perhaps nobody is going to pay 1 million dollars all by him/herself so 
> instead I am going to give crowd funding a try ! ;)

It's absolutely possible to decode static huffman in parallel 
just start decoders off at all different offsets and when you reach
that part reject the output that was computed starting with the wrong offset.

It may pe possible to imply the correct offet by examineing the
bitstream, but this is not possible for all huffman tables, and is a
gross waste of resources.

If you want fast static huffman decoding, use an FPGA, they are
ideally suited.

[toc] | [prev] | [next] | [standalone]

#2020

Hmmm.. I was expecting the usefull truck full of horse shit... but so far 
the responses have been intelligent and some even surprising and insight 
full.

You are indeed close to figuring out my algorithm... but some concepts are 
still missing ;)

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#2021

On 9/12/2013 8:31 AM, Jasen Betts wrote:
> On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
>> Hello,
>>
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>>
>> It's always funny to see how some programmers believe that Huffman cannot be
>> decoded in parallel.
>>
>> I believe it is possible to decode (static) huffman in parallel.
>>
>> However as I wrote in the past I want a million dollars for it ! ;)
>>
>> Perhaps nobody is going to pay 1 million dollars all by him/herself so
>> instead I am going to give crowd funding a try ! ;)
>
> It's absolutely possible to decode static huffman in parallel
> just start decoders off at all different offsets and when you reach
> that part reject the output that was computed starting with the wrong offset.
>
> It may pe possible to imply the correct offet by examineing the
> bitstream, but this is not possible for all huffman tables, and is a
> gross waste of resources.
>
> If you want fast static huffman decoding, use an FPGA, they are
> ideally suited.
>


for one of my ideas for a video codec, I had considered the possibility 
of starting each row of macroblocks on a byte-aligned address (and with 
a zeroed DC predictor), which could potentially allow a decoder to have 
the ability to decode each row of macroblocks in a separate thread 
(as-needed).

haven't actually done this though...

[toc] | [prev] | [next] | [standalone]

#2024

"BGB"  wrote in message news:l0tmvj$5ac$1@news.albasani.net...

On 9/12/2013 8:31 AM, Jasen Betts wrote:
> On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
>> Hello,
>>
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>>
>> It's always funny to see how some programmers believe that Huffman cannot 
>> be
>> decoded in parallel.
>>
>> I believe it is possible to decode (static) huffman in parallel.
>>
>> However as I wrote in the past I want a million dollars for it ! ;)
>>
>> Perhaps nobody is going to pay 1 million dollars all by him/herself so
>> instead I am going to give crowd funding a try ! ;)
>
> It's absolutely possible to decode static huffman in parallel
> just start decoders off at all different offsets and when you reach
> that part reject the output that was computed starting with the wrong 
> offset.
>
> It may pe possible to imply the correct offet by examineing the
> bitstream, but this is not possible for all huffman tables, and is a
> gross waste of resources.
>
> If you want fast static huffman decoding, use an FPGA, they are
> ideally suited.
>


for one of my ideas for a video codec, I had considered the possibility
of starting each row of macroblocks on a byte-aligned address (and with
a zeroed DC predictor), which could potentially allow a decoder to have
the ability to decode each row of macroblocks in a separate thread
(as-needed).

haven't actually done this though...


Skybuck:

Why don't you stick to something like basket weaving, it's harder to fuck up 
and no serious consequences.  I don't think you have the brains to 
successfully do the technical stuff.

Shaun

[toc] | [prev] | [next] | [standalone]

#2028

Lol,

Well indiegogo seems to be a bust.

The best idea ever was removed. (Bitcoin Bussiness Patent, apperently it was 
not allowed.)

Also logging in problems weird.

Unfortunately kickstarter is not yet available in The Netherlands.

Also kickstarter also had problems... could not complete the last phase of 
the project.

Both websites very slow unfortunately. Indiegogo performed a little bit 
better.

When kickstarter is available in The Netherlands, you can invest safely in 
my projects.

Hopefully by that time it will either work better or my PC be new/faster ;)

Cause if it dont work out you get your money back.

If it does work out... everybody be happy ! ;) =D

[toc] | [prev] | [next] | [standalone]

#2027

On 12.09.2013 06:37, Skybuck Flying wrote:
> Hello,
>
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
> It's always funny to see how some programmers believe that Huffman
> cannot be decoded in parallel.
>
> I believe it is possible to decode (static) huffman in parallel.

"It depends". Either, you add synchronization markers (or unique 
symbols) to restart from. In such a case, you can launch several 
decoders at once, but first need to find suitable anchor-points to start 
decoding from. Or, you "hope" that Huffman self-synchronizes, which it 
often does, and try to eliminate bogus output later.

In either case, you will often find that the price for detecting the 
sync markers or the fixup is not worth running the Huffman in parallel. 
Essentially, the pre-scan or post-fixup is of approximately the same 
complexity as the Huffman itself (i.e. "simple"), so it's usually not 
worth bothering. For that to work, the blocks should relatively large, 
and the Huffman resync positions relatively regular so you can avoid 
complicated scanning. This again causes encoder complexity to go up 
somewhat.

Thus, there is no "general receipt" that works in all cases. It's very 
problem dependent whether such a thing makes sense or not.

Greetings,
	Thomas

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web