I actually take a keen interest in how to parallelize this type of stuff. I work as a CPU architect these days, and some of the algorithms we have to cope with (on finite, tiny hardware with budgets measured in milliWatts) are horribly serial. Meanwhile, our primary pathway to greater performance is to go parallel in one way or another. Parsing of various sorts is a recurring dragon to slay. In the embedded media space, the parsing problem usually takes on the form of Huffman decode, or lately arithmetic decode. (CABAC in H.264 is murder. Look it up some time if you care to be suitably horrified.) That is, we're not typically running lex and yacc, but rather decoding a video bitstream. In many cases, about the only parallelism we seem to get out those problems is through pipelining across multiple processors: Use a dedicated coprocessor to pull the bitstream apart and let the main CPU work the rest of the problem. Not very satisfying to a performance junkie, but hey, what can you do?
I agree with you on the nature of the paper. For most processing tasks, they just assumed infinite CPUs, so that it didn't matter at all how wide their algorithm got, it only mattered how shallow it got. In the end, the number of processors is finite, and that wide algorithm gets sequenced. It's a bit like saying you can implement any logic function of any number of variables in only two levels of logic. Sure, that's true if you have NAND gates with arbitrarily large numbers of inputs, arbitrarily large drive strength and wires that are infinitely fast. I think it would take significant amounts of unobtainium to build it though.:-)
Hmmm.... I had thought about precisely the sort of approach the CM guys describe, and had rejected it. Sure, you can use the formulation they give, but due to the non-linear nature of the state-space, you end up wasting most of your computation. They indicate log n time for parsing, but the computational cost (CPU cycles used) is going to be more like O(n * m), where m is the average number of possible input states for each character. The latency got shorter, sure, but the computational workload got tremendously larger. You may be much better off with a mostly serial parser feeding a parallel compute engine the semantic meaning of the program.
I've personally applied and have seen applied a very restricted form of this approach on machines with large amounts of instruction-level parallelism. Basically, start processing the next symbol before the current symbol is fully resolved. You may have to speculate on some aspects of the next symbol, but if you have enough of the subsequent context worked out, your speculation won't get out of hand. This is useful for reducing latency and using up otherwise idle resources. I've applied it to several VLD-style algorithms. But, as the potential incoming state space explodes, the resource requirements explode as well, so there's a natural limit to how much of this you can really do.
In the language of the article, most parsing problems look like the "FSM dwarf," and they really are embarrassingly serial problems. Edge detection and pattern recognition on images is different because they're identifying spatial contexts, and that can be done in a parallel manner. The meaning of that spacial context depends on the neighborhood around the pixel. Language parsing (whether natural language or a computer programming language) is somewhat different, as the meaning of each new token is directly influenced by the tokens that precede it, and typically not the tokens that follow it.
For example, suppose you're parsing a perl program with this single-character-per-processor paradigm. You see the character '}'. What does it mean? Is it:
Closing a block, as in "if (foo) { blah; }"?
Closing a hash reference, as in "$hash{blah}"?
Closing a dereference, as in "@{$foo}"?
Is it part of a string?
Is it part of a comment?
About the most you might be able to do is coordinate with nearby processors and identify potential tokens. Once you have those tokens, though, they need to go into the parser state machine in order to make their semantics known to the computer.
Really, the only parallelism you have is in terms of pipeline stages. Many parsers are divided up into two main stages: lexical analysis and semantic analysis. (Look up lex and yacc for an implementation of this model.) You could run the lexer on one CPU and the grammar on another. Whatever program this drives could run on other CPUs.
It's not enough to merely limit yourself to NOT, XOR and pass-through, as traditional implementations still destroy information in a way. Traditional gates are made of switches: When you switch the input to an inverter (NOT gate) off, the output switches on by closing a switch to Vdd and opening the switch to ground. Some current flows from Vdd to the inputs of whatever gates the inverter is driving. When you switch the input to that inverter on, the switch to Vdd opens and the switch to ground closes. That charge that had been on the output of the gate driving other inputs now gets drained to ground. That's where a good portion of the power gets burned in a CMOS circuit. The new output destroys the old output.
And then there's other sources of inefficiency. While switching, there's a point where both switches are neither fully open nor fully closed, and you get direct flow-through from Vdd to GND. That adds to the power consumption as well. And finally, the switches aren't perfect. An "open" switch still lets a little current "leak" through. This is referred to as leakage power.
This site has some logic gates that are designed specifically for reversible computation.
--Joe
Decompressing and recompressing in the *same* format can be lossless, if the encoder is well matched to the original encoder. Typically, though, even that increases the SNR, since the re-encoder is seeing a different input than the original encoder.
I authored an Intellivision emulator and a development kit for Intellivision. I've got a decent portion of the free Intellivision emulator market, and pretty much all of the dev-kit market. Sure, that's an active audience measured in the dozens, but I'm happy.:-)
Err, yes. Statutory damages. I forgot and you are correct. You are always entitled to actual damages. Statutory damages are the scary ones most of the time.
In the US, if you have an unregistered copyright, the most you can do is put out a cease and desist. The DMCA takedown notices fall under that heading, I believe, and this particular takedown seems to fall under the "distortion/mutilation" clause here. To sue for damages, you must have a registered copyright. Also, you can only sue for damages for infringement that occurs after the copyright was registered (with a minor exception for registration applications within 3 months of publication).
One of the Strong Bad toons on Homestar Runner did something similar. HRWiki says they apparently changed the tune to Hot Cross Buns though for the DVD. Hmmm...
Not after the DMCA. Circumventing an access control is a criminal act under the DMCA. Using a hacked key or similar is sufficient to meet that threshold.
I've been hearing variations on the "SHA-1 cracked" theme for awhile, for different definitions of "cracked." I believe the consensus has been for awhile now to move towards SHA-256 and other schemes.
Quantum entanglement certainly can't be used to transmit information faster than the speed of light. I was thinking along the lines of quantum encryption.
Hmmm... how many other long-distance forces are easily modulated and detected? Electromagnetic waves are pretty much the only game in town given the physics I'm aware of. I can't imagine, say, using gravity to implement the equivalent of our radio—too much energy required to move the transmitter, and requires too sensitive of a detector to receive. I guess maybe they could work out something that used quantum entanglement...
Now the real question is, will we instead end up finding a planet or other large body 25-30 light years away that's effective in sending us back our own broadcasts of I Love Lucy and Leave it to Beaver?
Which is all the more reason you're bellying up to buy a WhirrMaster-10000 to go screaming down the road in?
Just because someone else is being a dick cranking their music doesn't automatically make turbine whine attractive in an automobile, let alone salable. Lack of enforcement or under-enforcement of noise ordinances doesn't make me want to damage my own hearing within the (dis)comfort of my own car, and I imagine most people feel the same.
A "bye" in this context means "they will be excluded from the requirements." So, if you're flying from certain countries and you're a citizen of that country—e.g. Great Britain—you might not have to give a full print set, but if you're from others, you will. It's sense #1 in this definition.
I used to care about the difference between symbol rate and bit rate—heck, I am an architect at a company that made its fortunes in part through DSP-driven modems—and even my coworkers don't really care whether you refer to baud or bps, since typically the meaning is clear from context, and depending on what portion of the system you're referring to, the terms are interchangeable.
Go look at the stty man page. Go ahead, I'll wait. Now point to where it says "bps" or "bits per second." What? Can't find it there? But it says "baud?" Must've been written by non-technical people who don't know their terminology. BTW, I tried this experiment on Linux, Solaris, and for good measure, AIX. For the record, AIX does refer to "bits per second," but those intellectually lazy folk[*] at Sun refer to baud. And you can forget those Linux hippies.;-)
I used to fight "the good fight," correcting people on the difference between bps and baud, and correcting people for pronouncing GIF with a hard G. (Look! It says right here in the Compuserve spec that it's a SOFT G!) It's a great way to alienate people, including technical types. It's one thing to use the terminology correctly yourself, and to correct someone if they're using terminology incorrectly in a context where it matters, but to do it as a matter of course just makes you a PITA.
As for the "doss" vs. "dose," I had a number of teachers and other authority figures in the 1980s insist it was pronounced "dose," correcting me when I would pronounce it "doss." I believe they didn't realize it was an American acronym, and not derived from the Spanish word for "two."
Slashdot Mirror
I actually take a keen interest in how to parallelize this type of stuff. I work as a CPU architect these days, and some of the algorithms we have to cope with (on finite, tiny hardware with budgets measured in milliWatts) are horribly serial. Meanwhile, our primary pathway to greater performance is to go parallel in one way or another. Parsing of various sorts is a recurring dragon to slay. In the embedded media space, the parsing problem usually takes on the form of Huffman decode, or lately arithmetic decode. (CABAC in H.264 is murder. Look it up some time if you care to be suitably horrified.) That is, we're not typically running lex and yacc, but rather decoding a video bitstream. In many cases, about the only parallelism we seem to get out those problems is through pipelining across multiple processors: Use a dedicated coprocessor to pull the bitstream apart and let the main CPU work the rest of the problem. Not very satisfying to a performance junkie, but hey, what can you do?
I agree with you on the nature of the paper. For most processing tasks, they just assumed infinite CPUs, so that it didn't matter at all how wide their algorithm got, it only mattered how shallow it got. In the end, the number of processors is finite, and that wide algorithm gets sequenced. It's a bit like saying you can implement any logic function of any number of variables in only two levels of logic. Sure, that's true if you have NAND gates with arbitrarily large numbers of inputs, arbitrarily large drive strength and wires that are infinitely fast. I think it would take significant amounts of unobtainium to build it though. :-)
--JoeThanks for the paper reference! I appreciate it.
Hmmm.... I had thought about precisely the sort of approach the CM guys describe, and had rejected it. Sure, you can use the formulation they give, but due to the non-linear nature of the state-space, you end up wasting most of your computation. They indicate log n time for parsing, but the computational cost (CPU cycles used) is going to be more like O(n * m), where m is the average number of possible input states for each character. The latency got shorter, sure, but the computational workload got tremendously larger. You may be much better off with a mostly serial parser feeding a parallel compute engine the semantic meaning of the program.
I've personally applied and have seen applied a very restricted form of this approach on machines with large amounts of instruction-level parallelism. Basically, start processing the next symbol before the current symbol is fully resolved. You may have to speculate on some aspects of the next symbol, but if you have enough of the subsequent context worked out, your speculation won't get out of hand. This is useful for reducing latency and using up otherwise idle resources. I've applied it to several VLD-style algorithms. But, as the potential incoming state space explodes, the resource requirements explode as well, so there's a natural limit to how much of this you can really do.
--JoeIn the language of the article, most parsing problems look like the "FSM dwarf," and they really are embarrassingly serial problems. Edge detection and pattern recognition on images is different because they're identifying spatial contexts, and that can be done in a parallel manner. The meaning of that spacial context depends on the neighborhood around the pixel. Language parsing (whether natural language or a computer programming language) is somewhat different, as the meaning of each new token is directly influenced by the tokens that precede it, and typically not the tokens that follow it.
For example, suppose you're parsing a perl program with this single-character-per-processor paradigm. You see the character '}'. What does it mean? Is it:
About the most you might be able to do is coordinate with nearby processors and identify potential tokens. Once you have those tokens, though, they need to go into the parser state machine in order to make their semantics known to the computer.
Really, the only parallelism you have is in terms of pipeline stages. Many parsers are divided up into two main stages: lexical analysis and semantic analysis. (Look up lex and yacc for an implementation of this model.) You could run the lexer on one CPU and the grammar on another. Whatever program this drives could run on other CPUs.
--JoeOops, my bad. That site has abstract circuits and doesn't show the actual transistors. This paper shows some circuits.
It's not enough to merely limit yourself to NOT, XOR and pass-through, as traditional implementations still destroy information in a way. Traditional gates are made of switches: When you switch the input to an inverter (NOT gate) off, the output switches on by closing a switch to Vdd and opening the switch to ground. Some current flows from Vdd to the inputs of whatever gates the inverter is driving. When you switch the input to that inverter on, the switch to Vdd opens and the switch to ground closes. That charge that had been on the output of the gate driving other inputs now gets drained to ground. That's where a good portion of the power gets burned in a CMOS circuit. The new output destroys the old output.
And then there's other sources of inefficiency. While switching, there's a point where both switches are neither fully open nor fully closed, and you get direct flow-through from Vdd to GND. That adds to the power consumption as well. And finally, the switches aren't perfect. An "open" switch still lets a little current "leak" through. This is referred to as leakage power.
This site has some logic gates that are designed specifically for reversible computation. --Joe
Decompressing and recompressing in the *same* format can be lossless, if the encoder is well matched to the original encoder. Typically, though, even that increases the SNR, since the re-encoder is seeing a different input than the original encoder.
I authored an Intellivision emulator and a development kit for Intellivision. I've got a decent portion of the free Intellivision emulator market, and pretty much all of the dev-kit market. Sure, that's an active audience measured in the dozens, but I'm happy. :-)
--JoeErr, yes. Statutory damages. I forgot and you are correct. You are always entitled to actual damages. Statutory damages are the scary ones most of the time.
I think he had the single-player version in mind.
The videos?
In the US, if you have an unregistered copyright, the most you can do is put out a cease and desist. The DMCA takedown notices fall under that heading, I believe, and this particular takedown seems to fall under the "distortion/mutilation" clause here. To sue for damages, you must have a registered copyright. Also, you can only sue for damages for infringement that occurs after the copyright was registered (with a minor exception for registration applications within 3 months of publication).
That site in general is VERY informative reading.
--Joe...unless you put the work out in the public domain. I suppose you could use some other moderately permissive license as well.
One of the Strong Bad toons on Homestar Runner did something similar. HRWiki says they apparently changed the tune to Hot Cross Buns though for the DVD. Hmmm...
Well, there was that one line in the article about rhythmic force.... ;-)
Even the cuddliest creatures have their enforcers. :-)
Killer whales ARE dolphins. Quoting Wikipedia:
Not after the DMCA. Circumventing an access control is a criminal act under the DMCA. Using a hacked key or similar is sufficient to meet that threshold.
I've been hearing variations on the "SHA-1 cracked" theme for awhile, for different definitions of "cracked." I believe the consensus has been for awhile now to move towards SHA-256 and other schemes.
--JoeGo look up youtube-dl and ffmpeg. You're welcome.
Quantum entanglement certainly can't be used to transmit information faster than the speed of light. I was thinking along the lines of quantum encryption.
Is it because I need to know something about the angle of my brother's envelope, communicated before I open it?
Hmmm... how many other long-distance forces are easily modulated and detected? Electromagnetic waves are pretty much the only game in town given the physics I'm aware of. I can't imagine, say, using gravity to implement the equivalent of our radio—too much energy required to move the transmitter, and requires too sensitive of a detector to receive. I guess maybe they could work out something that used quantum entanglement...
Now the real question is, will we instead end up finding a planet or other large body 25-30 light years away that's effective in sending us back our own broadcasts of I Love Lucy and Leave it to Beaver?
--JoeWhich is all the more reason you're bellying up to buy a WhirrMaster-10000 to go screaming down the road in?
Just because someone else is being a dick cranking their music doesn't automatically make turbine whine attractive in an automobile, let alone salable. Lack of enforcement or under-enforcement of noise ordinances doesn't make me want to damage my own hearing within the (dis)comfort of my own car, and I imagine most people feel the same.
--JoeA "bye" in this context means "they will be excluded from the requirements." So, if you're flying from certain countries and you're a citizen of that country—e.g. Great Britain—you might not have to give a full print set, but if you're from others, you will. It's sense #1 in this definition.
For a factor of 100 difference, I care.
I used to care about the difference between symbol rate and bit rate—heck, I am an architect at a company that made its fortunes in part through DSP-driven modems—and even my coworkers don't really care whether you refer to baud or bps, since typically the meaning is clear from context, and depending on what portion of the system you're referring to, the terms are interchangeable.
Go look at the stty man page. Go ahead, I'll wait. Now point to where it says "bps" or "bits per second." What? Can't find it there? But it says "baud?" Must've been written by non-technical people who don't know their terminology. BTW, I tried this experiment on Linux, Solaris, and for good measure, AIX. For the record, AIX does refer to "bits per second," but those intellectually lazy folk[*] at Sun refer to baud. And you can forget those Linux hippies. ;-)
I used to fight "the good fight," correcting people on the difference between bps and baud, and correcting people for pronouncing GIF with a hard G. (Look! It says right here in the Compuserve spec that it's a SOFT G!) It's a great way to alienate people, including technical types. It's one thing to use the terminology correctly yourself, and to correct someone if they're using terminology incorrectly in a context where it matters, but to do it as a matter of course just makes you a PITA.
As for the "doss" vs. "dose," I had a number of teachers and other authority figures in the 1980s insist it was pronounced "dose," correcting me when I would pronounce it "doss." I believe they didn't realize it was an American acronym, and not derived from the Spanish word for "two."
--Joe
[*] Tongue planted firmly in cheek.