Live Business Chat
2015 Sep 06, 05:36:34 pm *
Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
News: This is a friendly non-profit discussion group about making money. Click the "NOTIFY" button every chance you get to receive instant alerts about new information. We don't like spam. If your first posts are about something you want from us, it is probably spam, and you will be banned in forums worldwide. No soliciting! If you have problems with the forum, contact badon in the business chat.
 
   Home   Help Search Calendar Login Register  
Pages: 1 [2] 3  All   Go Down
  Print  
Author Topic: Finally writing down Design and Engineering Notes  (Read 327 times)
0 Members and 2 Guests are viewing this topic.
JDługosz
Entrepreneur
**
Offline Offline

Posts: 65


« Reply #10 on: 2015 Aug 17, 11:48:14 pm »

Cohort:  http://dictionary.reference.com/browse/cohort?r=75&src=ref&ch=dic
It means a "group", and is often used to refer to partitioning data prior to acting on each cohort individually. 

Tools:  What compiler and IDE are you using?  For Visual Studio, it supports git automatically as of 2013 and has an extension available for 2012.    That might not help with copying the stuff from github in the first place.

Using a revision control system is important for any development work.  For shared/distributed development git is the rule.  (Subversion is still used for open source development, but is not handy for working disconnected from the network like you are.  git is "distributed" as a basic feature)

How about I gently teach you, a little at a time?
I assume you connect to the Internet with your development machine, but only connect on occasion.  So install msysgit on the development machine, and then you can issue the command

Code:
git clone https://github.com/jdlugosz/parNext.wiki.git  C:/path/parN/wiki

where "C:/path/" is wherever you want to put the files, and the slashes must be /this/kind/ or you might confuse the git program (msys allows Unix code to be built for Windows, so it wants the Unix-style path separator).

You'll now have all the same document files I do, in C:\path\parN\wiki, plus a directory named .git which contains information used by git.


The main part of github provides a button for downloading a single zip file, without needing to use git on your end.  I suppose they left that off the wiki part because they expect you to edit via the web interface.  Maybe the feature is still there, but hidden.

I could make a .zip (or .7z) file for you to download.  But that would not automatically keep up with changes.

I agree the Pages list box is not useful.  Even as a directory list of my document files, it is truncated.  I'll make a custom sidebar and other navigation things that the site provides.
Logged
Yutaka Sawada
Moderator
Capitalist Pig
*****
Offline Offline

Posts: 670


« Reply #11 on: 2015 Aug 19, 10:15:24 pm »

 Reading pages on "parNext" web-site reminds me old years of new PAR3 design. I tried many things, and did many mistakes. I learned some knowledge and got experience. I point some faults in the design notes.


Quote from: parNext
on [Goals] page; Choice of Algorithms, Hash

SHA-2 is king.
For light duty checking, with a very short check word, the Murmurhash can be used.

 It seems that each block has one hash value (SHA-2 or Murmurhash). Theoretically it can verify the completeness and detect the damage of blocks. But, it won't work in time actually, because SHA-2 (and maybe Murmurhash) is too slow. Even when MD5 is known as fast hash algorithm, it caused freeze (busy state) of PAR2 clients. Finding blocks on a damaged file requires longer time than you thought. When block size is 4KB (4096 bytes), it requires 4096 times more time than calculating hash of the file simply. Even when hashing a file requires only 0.1 seconds, it may require max 409 seconds (over than 6 minutes) to find a block on the damaged file.

 The point you forgot was that offset of a block might changed by damage (insert or deletion). While source blocks align in correct position on original source files, it may not on damaged files. Some special purpose (like DVDisaster) has no risk of this type, because it's impossible to move file data on DVD-R. Parchive should support all kinds of damage types for general usage.

 Now, you can see how other practical applications solve the problem. They use combination of rolling hash and strong hash. Rolling hash is used to locate blocks. Strong hash is used to verify blocks. This style is written on PAR2 specification, which uses CRC-32 and MD5. persicum's RSC32 uses CRC-64 and SHA-1/SHA-2/Blake2. rsync uses rolling checksum (modified Adlar-32) and MD5.


Quote from: parNext
on [Block Nomenclature] page;

There may be many more blocks than the ECC algorithm can handle at once. So, the data is chopped up into individual batches called  Cohorts .

 The design of "Cohort" (row in the picture of blocks) was called as "interleave", ago. It's a simple and fast method for short codes to treat many blocks. For example, DVDisaster uses 8-bit Reed-Solomon Error Correction Codes, which treats max 255 total Stripes (called as layers in DVDisaster). Though it cannot recover many damaged blocks in a Cohort, the risk seems to be low at the special usage. (protecting DVD media.)

 From reading "numbering and arrangement of the source blocks" page, you understand the problem of "Cohort" system. The recovering capability is worse than the redundancy. As there are many Cohorts, the recovering capability will become less. Even when you have 54 parity blocks, they cannot recover only 6 damaged blocks ! It's a fatal problem, and many parNext users will complain. (The number of possible recovery is min 5 blocks and max 54 blocks.)

 When I tried to design "interleaving" (Cohort you say) method ago, I came up with a solution for this problem. The idea was a parity of each Stripe. (similar to 2D parity check) In your example picture, there are 11 source blocks on a column. Calculate one parity block by XOR them (call it as XOR block to distinguish from normal parity block), and put the XOR block under the bottom row. It requires space of 10 or more blocks. (10 XOR blocks and some parity blocks for them.)

Code:
Adding one more row at the bottom;
[  1][  2][  3][  4]...[ 10] : [P 1][P12]...
[ 11][ 12][ 13][ 14]...[ 20] : [P 2][P13]...
[ 21][ 22][ 23][ 24]...[ 30] : [P 3][P14]...
...
[101][102][103][104]...[   ] : [P11][P25]...
[X 1][X 2][X 3][X 4]...[X10] : [XP1][XP2]

 Even when all source blocks on a row are lost, they can be recovered by XOR blocks at the bottom. To cause non-recoverable loss, it requires 6 * 2 = 12 damaged blocks. (The number of possible recovery is min 11 blocks and max 59 blocks.) Hmm, this may not improve the capability so much as compared with the number of additional blocks... Then, I understood that many Cohorts was bad idea.

 Those who know ECC algorithms objected my interleaving idea for PAR3. You should avoid setting many Cohorts as possible as you can. There is no reason to use Cohort from the point of mathematican's view. If you have more blocks than a ECC algorithm can handle, you just select another ECC algorithm which can treat them with ease. You don't need to stick one ECC algorithm. When blocks are very few, 8-bit Reed-Solomon Codes is quick. When blocks are several thousand, 16-bit Reed-Solomon Codes is enough. When blocks are more than ten thousand, something new technology like FFT is required to treat large redundancy. Michael Niedermayer suggested to use 16-bit Reed-Solomon Error Correction Codes with FFT. Mr. persicum suggested to use 32-bit Reed-Solomon Codes with FFT, which is fast for many blocks (max 1,048,576 blocks). When 32-bit isn't enough, LDPC can handle unlimited number of blocks in theory.

 And you should re-think that how many blocks are required really. I'm not sure why you want to set block size to be 4KB. To keep sector alignment, multiple of 4KB is enough. Though setting many source blocks is good for random error, too many blocks is inefficient and may become slow. I think that 16-bit Reed-Solomon Error Correction Codes (with new technology) will be the best for PAR3. (if I can implement it.) But, I cannot understand the complex theory at this time, hehe.
Logged
JDługosz
Entrepreneur
**
Offline Offline

Posts: 65


« Reply #12 on: 2015 Aug 20, 01:47:46 am »

I learned some knowledge and got experience. I point some faults in the design notes.

Great!  I'll read this thoroughly and document what has been learned.
Logged
JDługosz
Entrepreneur
**
Offline Offline

Posts: 65


« Reply #13 on: 2015 Aug 20, 02:16:04 am »

The recovering capability is worse than the redundancy.

I have some calculations now: With 20 cohorts and 20 stripes, adding 10 stripes of Parity (50% increase in size), with 20% random damage, will have a 6.1% chance to fail to correct any cohort, 45% chance that there will only be one bad row, and 99% chance of 5 bad rows.  So, 50% increase can't handle 40% damage.

Instead of straight rows and columns (cohorts and stripes), using overlapping cohorts and more complex patterns (like your 2-D), is beyond my statistical mathematics skills.  I'm going to create a general purpose test program that can simulate any kind of cohort arrangement, and see what random trials produce. 

To compare the results I noted above, I want to see what happens if I use a "2D" pattern with 5 Parity stripes one way and 5 stripes another way.  With the same 50% added data, fewer recovery blocks "across" means you'll have 15 out of 20 unrecovered rows.  But the ones that *are* recovered populate sites for use by the "up-and-down" ECC cohorts.  Even so, there are still 20% bad.  BUT that populates more for the "across" to try again... and at this point it's too unreliable to figure out mathematically and I'll put work into full MonteCarlo simulations instead.

I *suspect* that using overlapping cohorts will give synergy.  Taking the extreme limit of this, it looks like how "Raptor" etc. works, so I think that is right.

Quote
If you have more blocks than a ECC algorithm can handle, you just select another ECC algorithm which can treat them with ease.
In general, one big formula that requires *all* source blocks for *every* ECC block will put demands on the computer.  Ideas like LDPC are nothing more than "fancy patterns" of small cohorts against a simple ECC algorithm! 

In this case, "cohort" is not the best word, though, and I should improve the nomenclature.  For software engineering, I find it is best to use a *unique* word for a particular concept or design feature, especially when casual descriptive words are used in many places.  Is there a Japanese word for a "grouping" that is interestingly poetic in its connotations?

1,048,576 blocks is interesting:  With 4K blocks, that is 4GB and it all fits in RAM on a 64-bit computer.   However, 4GB isn't large enough for movie discs anymore, either: a BD holds 25 or 50GB. 
Logged
Yutaka Sawada
Moderator
Capitalist Pig
*****
Offline Offline

Posts: 670


« Reply #14 on: 2015 Aug 21, 07:09:36 pm »

Quote from: JDlugosz
What compiler and IDE are you using?

 I use Visual Studio 2008. It's the last version, which can work without internet.

Quote
How about I gently teach you, a little at a time?

 No, thank you. Though I appreciate you help, there's no need to hurry.

Logged
Yutaka Sawada
Moderator
Capitalist Pig
*****
Offline Offline

Posts: 670


« Reply #15 on: 2015 Aug 23, 10:11:02 pm »

Quote from: JDlugosz
at this point it's too unreliable to figure out mathematically

 I think so, too. I consider your example blocks of 20 * 20, and what happens in 2-D style. I put the sample pattern below;

Code:
400 source blocks (20 columns * 20 rows);

[  1][ 21][ 41]...[361][381]

[  2][ 22][ 42]...[362][382]
[  3][ 23][ 43]...[363][383]
...
[ 19][ 39][ 59]...[379][399]
[ 20][ 40][ 60]...[380][400]


 Case of adding 200 horizontal parity blocks (10 columns * 20 rows);

[  1][ 21][ 41]...[361][381] = [  1][ 21][ 41]...[161][181]
[  2][ 22][ 42]...[362][382] = [  2][ 22][ 42]...[162][182]
[  3][ 23][ 43]...[363][383] = [  3][ 23][ 43]...[163][183]
...
[ 19][ 39][ 59]...[379][399] = [ 19][ 39][ 59]...[179][199]
[ 20][ 40][ 60]...[380][400] = [ 20][ 40][ 60]...[180][200]


 Case of adding 100 horizontal parity blocks (5 columns * 20 rows)
and 100 vertical parity blocks (20 columns * 5 rows);

[  1][ 21][ 41]...[361][381] = [  1][ 21][ 41][ 61][ 81]
[  2][ 22][ 42]...[362][382] = [  2][ 22][ 42][ 62][ 82]
[  3][ 23][ 43]...[363][383] = [  3][ 23][ 43][ 63][ 83]
...
[ 19][ 39][ 59]...[379][399] = [ 19][ 39][ 59][ 79][ 99]
[ 20][ 40][ 60]...[380][400] = [ 20][ 40][ 60][ 80][100]
  H    H    H       H    H
[  1][  2][  3]...[ 19][ 20]
[ 21][ 22][ 23]...[ 39][ 40]
[ 41][ 42][ 43]...[ 59][ 60]
[ 61][ 62][ 63]...[ 79][ 80]
[ 81][ 82][ 83]...[ 99][100]


 In the normal "Cohort" style "With 20 cohorts and 20 stripes, adding 10 stripes of Parity (50% increase in size)", it can recover max 200 source blocks. Because max 10 lost blocks per each rows, the failed case is 11 lost blocks. So, the range of recovering capability is "min 10 and max 200, by 200 parity" blocks. 50% redundancy can recover 2.5% to 50% source blocks.

 In the 2-D style, horizontal parity can recover max 5 blocks per each row, and vertical parity can recover max 5 blocks per each column. Then, max number of recoverable blocks is (5 * 20) + (20 * 5) - (5 * 5) = 175 blocks. The failed case requires 6 blocks in both directions, thus 6 * 6 = 36 lost blocks is failed. So, the range of recovering capability is "min 35 and max 175, by 200 parity" blocks. Though min is increased by 25, max is decreased by 25 also, then average may be same. 50% redundancy can recover 8.75% to 43.75% source blocks.


Quote
Is there a Japanese word for a "grouping" that is interestingly poetic in its connotations?

 No, I don't know.
Logged
JDługosz
Entrepreneur
**
Offline Offline

Posts: 65


« Reply #16 on: 2015 Aug 24, 01:39:47 pm »

I use Visual Studio 2008. It's the last version, which can work without internet.


I use 2010 at work, and I don't know anything that requires Internet access.  It has a "news" page on start up (which can be turned off) but the compiler, debugger, etc. don't need Internet access for anything and I've never seen it try.

I found VS10 (2010) to be compelling because of new language features, such as lvalue references.
Logged
Yutaka Sawada
Moderator
Capitalist Pig
*****
Offline Offline

Posts: 670


« Reply #17 on: 2015 Aug 28, 06:51:10 pm »

Quote from: JDlugosz
don't need Internet access for anything and I've never seen it try.

 Maybe programming style is different. Because I don't know Windows API or language manner so much, I refer help documents very much, while I write code. The help documents for VS2010 requires Internet. Though I installed VS2010 on my PC at first, I un-installed it and installed VS2008 next. I tested both versions, and VS2008 is more light and easy to use. At this time, there is no problem in VS2008 for me.

Quote
However, 4GB isn't large enough for movie discs anymore, either: a BD holds 25 or 50GB.

 There are some FFT possible primes for 32-bit prime based Reed-Solomon Codes. (Fermat prime is the best for 16-bit prime based Codes.) Form of "constant * (2 ** n) + 1" seems to be good for FFT. (in this text, ** means power.) For example, Fermat prime 32769 = 32768 + 1 = 1 * (2 ** 16) + 1. I tested a maybe biggest 32-bit prime 4293918721 = 4095 * (2 ** 20) + 1 ago, which support max 1048576 blocks (2 ** 20).

 From reading my old (6 years ago !) note, there are some smaller primes for more blocks. A 32-bit prime 2151677953 = 513 * (2 ** 22) + 1 supports max 4194304 blocks (2 ** 22). A 32-bit prime 3221225473 = 3 * (2 ** 30) + 1 supports max 1073741824 blocks (2 ** 30). I'm not sure there are other possible primes. persicum might select something good prime in his RSC32.

 So, theoretical max number of total blocks may be 1073741824 blocks (2 ** 30). Only loading one element (4-bytes) requires 4GB memory. =P 4KB block size and 536870912 blocks (2 ** 29) can cover 2TB source data. It must be enough for normal usage. But, the speed of both File IO and Calculation will be the problem. =X While persicum stated that it was possible to perform enough speed in 32-bit Reed-Solomon Codes, I could not reach his level. Anyway, I am doubtful about the worth of more blocks than the range of 16-bit.
Logged
Nyan
Dreamer
*
Offline Offline

Posts: 5


« Reply #18 on: 2015 Aug 29, 05:32:34 pm »

I've not tried it, but you can still download the offline MSDN documentation: https://www.microsoft.com/en-us/download/details.aspx?id=34794

Looks like 2013 is there, I don't know whether they will release one for VS2015.

But if 2008 works fine for you, then that's all fine Smiley

I've been looking at writing my own PAR2 implementation and wondering about extending the SSSE3 implementation to AVX2 (or AVX512 if that ever appears), which VS2008 doesn't support.  Maybe it's not of interest to you since AVX2 support is still very limited.
Logged
Yutaka Sawada
Moderator
Capitalist Pig
*****
Offline Offline

Posts: 670


« Reply #19 on: 2015 Aug 31, 09:48:31 pm »

Quote from: Nyan
you can still download the offline MSDN documentation

 I downloaded Windows SDK for Windows 7. Because I don't use later Windows 8/8.1/10, current one is enough for me. I don't know why it's impossible to download documents of Visual Studio 2010 as DVD format. My PC's CPU doesn't support AES/AVX/AVX2, so I'm not interested in using them. If many users want to access, I may try like I implemeted SSSE3 on Pentium 3 (even SSE2 was un-available, hehe). I used yasm/masm to treat new CPU commands in independent ASM file ago, but it's difficult to write 64-bit ASM code nowadays. If Visual Studio 2008 becomes obsolate in future, I may use MinGW. (GCC with Windows API)
Logged
Pages: 1 [2] 3  All   Go Up
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.025 seconds with 18 queries.