Repository navigation
Add code examples #52
Description
Activity
- changed the title
[-]Add code examples to fft/convovle functions documentation[/-][+]Add code examples to documentation[/+]on Dec 11, 2015 - changed the title
[-]Add code examples to documentation[/-][+]Add code examples[/+]on Sep 14, 2016 Could an example(s) be added for those new to programming for GPU's? I've done a bit of OpenCL logic for adding an algorithm to the Hashcat project, but there was more freedom compared to how ArrayFire seems to restrict you to working with arrays?
// FNV-1a (32-bit) hashing algorithm fn main() { let key = [0x68, 0x65, 0x6c, 0x6c, 0x6f]; // "hello" let mut hash: u32 = 2166136261; // Hash init value defined by algorithm for byte in key.iter() { hash ^= *byte as u32; hash *= 16777619; // Another magic number defined by the algorithm } println!("Hash is: {:x}", hash); // 4f9f2cab }
Really simple code, take a string key as bytes and XOR them + multiply hash by a fixed value iteratively. With a large set of keys, how do you approach this in ArrayFire? Do you treat each key as a 1D array(column/ horizontal?) and rows of keys? If so does this mean I can only work on fixed string key lengths?
hashwould be used as a constant to fill another array for the operations?This example would make me think that I should have an array for each letter position(5 in this case + 1 for the hash)? Also curious about optimizing/setting up the array and data right, no idea if 3rd/4th dimensions are helpful for this or row/column optimal sizes for performance, my actual algorithm is doing about 32 billion hashes a second with OpenCL and Hashcat, I'm wanting to see how ArrayFire compares.
I have a slightly more complicated hash algorithm to implement which starts with a
while(length >= 24)operating on 24 bytes of the string key at a time for 3 64-bit unsigned integers. After that it handles the remaining <23 bytes a little differently. Both stages end with a call to an expensive function involving the 3 64-bit values being "mixed" with subtraction, XORing and bitshifting(both directions).I can share C/OpenCL/Rust implementations I've done, if it'd be worthwhile how a fairly straightforward algorithm with loop/conditional/arithmitic diffs/ports to ArrayFire?
I've had a try at porting the simple algorithm, wasn't too difficult with the one fixed key. Tried to add some dynamic strings and ran into memory issues somewhere between 625 and 3125 elements spread over 5 arrays. Code and discussion can be found on this Rust reddit post.
Any tips on what I'm doing wrong and could try? Or would ArrayFire not be the appropriate choice for this type of work on the GPU? I'm thinking I need to do the permutations via ArrayFire in GPU memory via some batching/loop?
I think the variable
hashesof type Array is incorrect. You are passing
in a slice of one value and passing in dims which seems to be a vector.On Tue, Oct 18, 2016, 4:44 PM Brennan Kinney notifications@github.com
wrote:I've had a try at porting the simple algorithm, wasn't too difficult with
the one fixed key. Tried to add some dynamic strings and ran into memory
issues somewhere between 625 and 3125 elements spread over 5 arrays. Code
and discussion can be found on this Rust reddit post
https://www.reddit.com/r/rust/comments/5836mf/working_with_arrayfire_and_large_arrays/
.Any tips on what I'm doing wrong and could try? Or would ArrayFire not be
the appropriate choice for this type of work on the GPU? I'm thinking I
need to do the permutations via ArrayFire in GPU memory via some
batching/loop?—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#52 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADHnOr7hDiVo4JeXFdfdXb4lfQpPlEnVks5q1KnngaJpZM4GzyTy
.A small clarification, I was referring to the variable hashes from the code
stub you posted on Reddit.On Tue, Oct 18, 2016, 7:48 PM Pradeep Garigipati pradeep@arrayfire.com
wrote:I think the variable
hashesof type Array is incorrect. You are passing
in a slice of one value and passing in dims which seems to be a vector.On Tue, Oct 18, 2016, 4:44 PM Brennan Kinney notifications@github.com
wrote:I've had a try at porting the simple algorithm, wasn't too difficult with
the one fixed key. Tried to add some dynamic strings and ran into memory
issues somewhere between 625 and 3125 elements spread over 5 arrays. Code
and discussion can be found on this Rust reddit post
https://www.reddit.com/r/rust/comments/5836mf/working_with_arrayfire_and_large_arrays/
.Any tips on what I'm doing wrong and could try? Or would ArrayFire not be
the appropriate choice for this type of work on the GPU? I'm thinking I
need to do the permutations via ArrayFire in GPU memory via some
batching/loop?—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#52 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADHnOr7hDiVo4JeXFdfdXb4lfQpPlEnVks5q1KnngaJpZM4GzyTy
.23 remaining items
That is true, I was referring to parallelization of the algorithm w.r.t single input stream of bytes.
Sure, hashing on a batch of inputs is trivially parallel, not doubt about that. However, at the moment there is no efficient way to do fnv-1a hash on even one input using ArrayFire. The reason I say that is accessing individual elements from GPU memory using indexing is going to be very inefficient, and it would have to individual element access because of data dependency across iterations.
Having said that, a custom kernel is going to be different approach all together and can most likely be more efficient. If you are requesting hashing support via a function in upstream - ArrayFire, then the request has to be moved an issue on upstream repository.
I am curious as to how you managed to do FNV-1a on single input byte stream using ArrayFire efficiently. Is there a chance you have your old code archived somewhere ?
I am curious as to how you managed to do FNV-1a on single input byte stream using ArrayFire efficiently. Is there a chance you have your old code archived somewhere ?
If I remember right, I believe I did something like take my charset ("abc" in this case) and created the permutations of the charset against the length(keyspace) where each new byte/index is a column, and the first column, then I could run the loop iterating against the columns.
I should have the old code somewhere I'll try to locate it for you.
If you are requesting hashing support via a function in upstream - ArrayFire, then the request has to be moved an issue on upstream repository.
No feature request afaik, I just wanted to know how to best handle this type of computation where I am needing to keep processing/iterating through permutations until a result being searched for is found, and be able to identify that input. The hashing algorithm itself shouldn't matter. If I can find the code it should make more sense :)
Reacted by Pradeep Garigipati@9prady9 My old code was in a bit of a messy state and I had some trouble getting it to run, but I've pieced together this example that seems to work now, it's only processing on 3 inputs instead of GB of permutations being generated on the GPU, but should show one of the ways I approached the hashing algorithm with ArrayFire:
use arrayfire as af; fn main() { // af::set_backend(Backend::CUDA);//Backend::OPENCL;//Backend::DEFAULT); af::init(); af::info(); ///////////////////////////////// // Generate string inputs to hash ///////////////////////////////// // Inputs are collapsed into a sequence/stream of bytes, single array dimension let test_strings = vec!["hello", "howdy", "hallo"]; let test_bytes = test_strings.iter() .flat_map(|s| s.as_bytes()) .cloned() .collect::<Vec<u8>>(); // println!("test_strings as byte array: {:?}", test_bytes); // [104, 101, 108, 108, 111, 104, 111, 119, 100, 121, 104, 97, 108, 108, 111] /////////////////////////// // Initialize values for AF /////////////////////////// // Used to size AF array dimensions let input_len = test_strings[0].len() as u64; let num_inputs = test_strings.len() as u64; // Convert to an ArrayFire 2D array (Column Major) // 5x3 col(length of bytes for input) x row(number of inputs) let inputs_dims = af::Dim4::new(&[input_len, num_inputs, 1, 1]); // [5, 3, 1, 1] let inputs = af::Array::new(&test_bytes, inputs_dims); // Each input now has it's bytes in it's own column // print(&inputs); // [5 3 1 1] // 104 104 104 // 101 111 97 // 108 119 108 // 108 100 108 // 111 121 111 let fnv_dims = af::Dim4::new(&[1, num_inputs, 1, 1]); // [1, 3, 1, 1] //////////////////////////// // Compute hashes for inputs //////////////////////////// let hashes = fnv1a32_gpu(&inputs, fnv_dims); // print(&hashes); // [1 3 1 1] // 1335831723 3497709110 4182196071 // println!("hashes: {:x} | {:x} | {:x}", 1_335_831_723_u32, 3_497_709_110_u32, 4_182_196_071_u32); // 4f9f2cab | d07ace36 | f9473f67 /////////////////////// // Find matching hashes /////////////////////// // Creates an AF array filled with the same target value to match for, let target_hashes: af::Array<u32> = af::constant(0x4f9f2cab as u32, fnv_dims); // let target_hashes: af::Array<u32> = af::Array::new(&[0xf9473f67, 0x4f9f2cab], fnv_dims); let matches = check_for_matches(hashes, target_hashes); // println!("matched: {:?}", match_data); // matched: [1335831723] for matched in matches { println!("Matched the hash: {:x}", &matched); }; // Matched the hash: 4f9f2cab } // FNV-1a (32-bit) hashing algorithm const FNV_OFFSET: u32 = 2_166_136_261; const FNV_PRIME: u32 = 16_777_619; pub fn fnv1a32_gpu(inputs: &af::Array<u8>, fnv_dims: af::Dim4) -> af::Array<u32> { let input_len = inputs.dims().get()[0]; let mut hashes = af::constant(FNV_OFFSET, fnv_dims); let prime = af::constant(FNV_PRIME, fnv_dims); // Iterates through all inputs(columns) in parallel a byte each at a time(row) for row_index in 0..input_len { hashes = (hashes ^ af::row(&inputs, row_index)) * ′ } hashes } fn filter_matches(array: &af::Array<u32>, bools: &af::Array<bool>) -> af::Array<u32> { let indices = &af::locate(bools); let mut idxr = af::Indexer::default(); idxr.set_index(indices, 0, None); af::index_gen(array, idxr) } fn check_for_matches(hashes: af::Array<u32>, target_hashes: af::Array<u32>) -> Vec<u32> { // If we computed the same hash value, then `eq()` will let us know which values matched let is_matched: af::Array<bool> = af::eq(&hashes, &target_hashes, false); // Only keep results that were matched let result = filter_matches(&hashes, &is_matched); // Transfer the matches to the host CPU to access let length = result.elements() as usize; let mut match_data: Vec<u32> = vec![0; length]; result.host::<u32>(&mut match_data); match_data }
As the data input to process is finite and not going to take long, there's no logic for continuing/stopping the computation if a match is found. I can try to get my GPU permutator code working again and share that if helpful, I think for the long duration processing, I wanted to create a streaming iterator and was blocked by GAT(Generic Associated Types) which is still not implemented in Rust.
Perhaps the above could still be refined into a useful example for ArrayFire? I could provide a similar non-ArrayFire version if you see value in this as an example of how to think/approach writing for the GPU with ArrayFire?
Thank you for digging up the old code.
As I said earlier, you are doing individual accesses here in the below section of code
// Iterates through all inputs(columns) in parallel a byte each at a time(row) for row_index in 0..input_len { hashes = (hashes ^ af::row(&inputs, row_index)) * ′ }
Sure, all these operations are async operations but access to bytes of single column of input is being accessed individually in each iteration of the loop which is what I said earlier is going to be inefficient. As in, it can done in a better way with a kernel written especially for this kind of hashing algorithm to run on a batch of inputs.
Reacted by Brennan KinneyOh? I had thought that it was taking the whole row and computing against that, instead of each being a separate access. I could always rework the data to use columns instead of rows, eg 3x5? Or is that the same problem?
Again, this particular part (hash algorithm) wasn't the performance concern I was having trouble with, it was identifying matches which involved transferring data to the host each time to lookup the matches to decide what to do next. In the above snippet, I am only informed there was a match, not what the input value was.
Following approach instead retains an index before removing the unmatched elements:
fn check_for_matches(hashes: af::Array<u32>, target_hashes: af::Array<u32>) -> Vec<(usize, u32)> { // If we computed the same hash value, then `eq()` will let us know which values matched let is_matched: af::Array<bool> = af::eq(&hashes, &target_hashes, false); // Any unmatched value becomes 0 let result = af::mul(&hashes, &is_matched, false); // Transfer the matches to the host CPU to access let length = result.elements() as usize; let mut match_data: Vec<u32> = vec![0; length]; result.host::<u32>(&mut match_data); let results: Vec<(usize, u32)> = match_data.into_iter() .enumerate() .filter(|&(_,val)| val!=0) .collect(); // println!("results: {:?}", results); // results: [(0, 1335831723)] results } // ... main() let matches = check_for_matches(hashes, target_hashes); for (index, value) in matches { println!( "Matched the hash: {:x}, original input was: {:?}", value, test_strings[index] ); }; // Hash is: 4f9f2cab, input: "hello"
According to my notes, multiplying the bool array was faster than the
locateapproach too.
it can done in a better way with a kernel written especially for this kind of hashing algorithm to run on a batch of inputs.
How does one go about writing these kernels? I take it that's outside of ArrayFire? Is that direct OpenCL/CUDA code? One that would be of interest is AES CBC 256-bit decryption, I guess that's something where a custom kernel would be useful too?
Oh? I had thought that it was taking the whole row and computing against that, instead of each being a separate access. I could always rework the data to use columns instead of rows, eg 3x5? Or is that the same problem?
Well, it is running on GPU except that the memory access is not continuous. Notice the elements of single input are being handled in the host side for loop. Each such value for every input in every iteration is
input_lenapart in GPU memory. It is valid algorithm, not efficient in terms of GPU memory access. If you transpose the input such that bytes of one stream are along dimension 1 i.e. row in ArrayFire (ArrayFire follows column major order), then each run that is handling the xor and*operations for a single byte for all input streams is accessing continuous memory. This should give a better runtime than earlier.Having said that, I still believe a custom kernel can be written for this algorithm that can be faster than my above suggestion.
locate
- What is the runtime you are getting for
locatefunction ? - what is the size of these Arrays, target_hashes/computed_hashes typically ?
- Did you time the logic that multiplies with zero, brings back the result to host, then finds the indices ? How much is that time ?
- What is the runtime you are getting for
Having said that, I still believe a custom kernel can be written for this algorithm that can be faster than my above suggestion.
Is there a example / documentation on approaching that?
What is the runtime you are getting for
locatefunction?I don't have specific time logged unfortunately, just the old comment about it.
what is the size of these Arrays, target_hashes/computed_hashes typically?
The input values would iterate through lengths, so for a given length, all inputs were that fixed length each, typical lengths would be 6-12 if I recall correctly. For the Jenkins hash which is more involved, it was being used on filepaths as inputs, those would be much longer but permutations were often a similar 6-12 length of the filename with the paths only permutating known directories.
Actual size of the array with permutations would depend on GPU memory, the number of permutations could be very large and require many hours if not days to brute force, it was similar to a popular software called Hashcat commonly used for password recovery. In my code I was moving permutation generation to the GPU and referred to it as "tiling" the charset, it would fit as many of those tiles to cover the keyspace in GPU memory and operate on in as few passes/iterations of inputs as possible. I have a Nvidia GTX 1070 with 8GB of VRAM, and used 6-8GB I think with GPU computing with high/full usage of the CUDA cores.
Did you time the logic that multiplies with zero, brings back the result to host, then finds the indices ? How much is that time ?
I timed most parts individually, there was a macro for it, possibly one for CPU and another that was ArrayFire specific, I would need to look through that code again. While I could probably run the code again with the timing logic added to compare for you, presently I'm only able to use the CPU backend I think. My system is low on disk space and can't install CUDA as a result, unsure about OpenCL.
Is there a example / documentation on approaching that?
I would have to think through it. Top of my head, it would most likely start similar to your OpenCL kernel implementation I believe. But one thing is certain, the data would have to laid out so that GPU global memory accesses from all threads are coalesced from input bytes for different streams are read. That is most obvious part. Then it would probably involve some loop unrolling for processing single input byte stream if we have prior knowledge of minimum number of bytes etc.
The input values would iterate through lengths, so for a given length, all inputs were that fixed length each, typical lengths would be 6-12 if I recall correctly. For the Jenkins hash which is more involved, it was being used on filepaths as inputs, those would be much longer but permutations were often a similar 6-12 length of the filename with the paths only permutating known directories.
I wonder how locate is throttling the operation if single input is so small and actual number of such inputs is huge which are run in parallel as they are independent operations. You should rearranging the data so that access to GPU memory is coalesced as I mentioned here
I timed most parts individually, there was a macro for it, possibly one for CPU and another that was ArrayFire specific, I would need to look through that code again.
If possible, please share the timing code. ArrayFire is better timed as an average of multiple runs given that there is device warmup cost and kernel compilation of any functions used on their first call. Also, multiple JIT operations coalesce into single kernel, if you are timing individual statements you are likely doing more work than necessary - ArrayFire JIT operations are better timed a whole functional unit.
Reacted by Brennan KinneyAlso let us more move this discussion to slack or perhaps another issue as we moved away from the issues original intent some time back :) which is "code examples". Feel free to raise another issue with relevant details or we can discussion slack DM.
Reacted by Brennan Kinneyas we moved away from the issues original intent some time back :) which is "code examples".
Probably would make more sense to rename this issue and recreate the "Add code examples" one as a new issue at this point 😅
I've created a new issue regarding where the bulk of this thread ended up focusing on, I'll try find some time to meet your requests for the additional code and data layout change. Do you want me to continue sharing code fences on the issue thread comments, or would a repo be preferred?
Feel free to raise another issue with relevant details or we can discussion slack DM.
Not a slack user, I am fine with Discord, Facebook, email or a forum if you have one? Otherwise the github issue works well for me and might be helpful to someone else (although I guess this is a bit of a niche topic).
Probably would make more sense to rename this issue and recreate the "Add code examples" one as a new issue at this point 😅
Perhaps :) , I meant to have this issue as placeholder to keep updating examples, both standalone and documentation snippets - not specifically about any one particular one. So, I basically don't expect this issue to be closed anytime soon - at least not until every API has at least one example in documentation.
Thanks for moving the discussion to specific issue. GitHub issue works fine for us, just didn't wanted too much of specific discussion in placeholder issue.
Reacted by Brennan KinneyI'd appreciate keeping the history of the discussion here, so if wanting to hide the lengthy discussion, please consider marking as outdated/off-topic rather than deleting :)
I'd appreciate keeping the history of the discussion here, so if wanting to hide the lengthy discussion, please consider marking as outdated/off-topic rather than deleting :)
👍 I am not deleting anything, just wanted to move it to a separate issue so that this issue doesn't get too populated with auxiliary/tangential conversation.
Reacted by Brennan Kinney
Metadata
Metadata
Assignees
Type
Projects
- Status