google transpile error need help about fully-homomorphic-encryption HOT 13 CLOSED

I've reduced your example to the following slightly simplified subset (with no recursive calls or structs) and it still times out when compiling

#pragma hls_top
void sort(int list[10], char L, char R) {
  char i, j;
  int pv;
  int tmp;

  i = L;
  j = R;

  pv = list[(L + R) / 2];

#pragma hls_unroll yes
  for (char k = 0; k < 4; k++) {
#pragma hls_unroll yes
    for (char ki = 0; ki < 4; ki++) {
      if (list[i] < pv) break;
      i++;
    }

#pragma hls_unroll yes
    for (char kj = 0; kj < 4; kj++) {
      if (pv < list[j]) break;
      j--;
    }

    if (i >= j) break;

    tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;

    i++;
    j--;
  }

However, when I remove the second nested loop, it compiles after about 3 minutes.

This project uses xlscc, which in turn uses a solver to prove the compiled code terminates before unrolling the loops within. It seems that their solver is having difficulty proving this code terminates. I can try tinkering with it to see if it's superficial, but I imagine your segfault may be related to this. I've also reached out to the XLS team internally to see if they can diagnose the issue.

from fully-homomorphic-encryption.

I have parametrized the length of "for loop" as below, and got another compile Error message.

List Test5::process(List x, int L, int R, int n) {

int i, j;
int pv;
int tmp;

i = L;
j = R;

pv = x.list[(L + R)/2];

#pragma hls_unroll yes
for(int k=0; k<n; k++){

      #pragma hls_unroll yes
      for(int ki=0; ki<n; ki++){
            if(x.list[i] < pv)
              break;

            i++;
      }

      #pragma hls_unroll yes
      for(int kj=0; kj<n; kj++){
            if(pv < x.list[j])
              break;

            j--;
      }

Use --sandbox_debug to see verbose messages from the sandbox
Parsing file 'transpiler/examples/test5/test5.cc' with clang...
Generating IR...
UNIMPLEMENTED: Param not implemented in IrInterpreter
Target //transpiler/examples/test5:test5_tfhe.transpiled_files failed to build
Use --verbose_failures to see the command lines of failed build steps.
INFO: Elapsed time: 9.180s, Critical Path: 0.99s
INFO: 2 processes: 2 internal.
FAILED: Build did NOT complete successfully

from fully-homomorphic-encryption.

What is the build rule you set up for this one (i.e., the params to fhe_cc_library)? I think this is a missing feature from the interpreter=True for optimizer=xls, and you might be able to bypass it by using optimizer=yosys

from fully-homomorphic-encryption.

For context, this is the line it's hitting https://github.com/google/xls/blob/52c8e7e30dfa25cbafe99815f80d214c414364dd/xls/interpreter/ir_interpreter.cc#L720

Though if it's failing at the step of generating the IR, that may not be what I mentioned in the previous comment...

from fully-homomorphic-encryption.

Oh I think I see now. When n is an argument to the function then it can't unroll the loop because it doesn't know how many iterations to unroll. For any FHE program, all loops need to have statically-known bounds. And in this case the number of iterations of the loop is going to be converted by the compiler to an encrypted parameter, so this is simply not possible.

from fully-homomorphic-encryption.

Thank you for your reply.
I understand parametrized length of "for loop" is not possible.

Meanwhile, I removed the "break" controls from the code as below.
because transpile of "branch pruning" could be hard task for FHE.
But after about 3 hours compiling, I got the following error message.
I can not see what is going on.

root@2ea39926f6ce:/usr/src/fhe# bazel build -c opt //transpiler/examples/test6:test6_tfhe.transpiled_files
INFO: Analyzed target //transpiler/examples/test6:test6_tfhe.transpiled_files (0 packages loaded, 0 targets configured).
INFO: Found 1 target...
INFO: From Action transpiler/examples/test6/test6_tfhe.ir:
Parsing file 'transpiler/examples/test6/test6.cc' with clang...
Generating IR...
ERROR: /usr/src/fhe/transpiler/examples/test6/BUILD:5:15: Action transpiler/examples/test6/test6_tfhe.opt.bool.opt.ir failed: (Killed): bash failed: error executing command /bin/bash -c ... (remaining 1 argument(s) skipped)

Use --sandbox_debug to see verbose messages from the sandbox bash failed: error executing command /bin/bash -c ... (remaining 1 argument(s) skipped)

Use --sandbox_debug to see verbose messages from the sandbox
/bin/bash: line 1: 18264 Killed bazel-out/k8-opt-exec-2B5CBBC6/bin/external/com_google_xls/xls/tools/opt_main bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.opt.bool.ir --top $(cat bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.entry) > bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.opt.bool.opt.ir
Target //transpiler/examples/test6:test6_tfhe.transpiled_files failed to build
Use --verbose_failures to see the command lines of failed build steps.
INFO: Elapsed time: 12475.081s, Critical Path: 12474.02s
INFO: 8 processes: 2 internal, 6 processwrapper-sandbox.
FAILED: Build did NOT complete successfully
root@2ea39926f6ce:/usr/src/fhe#

-- code --

List Test6::process(List x, int L, int R) {

int i, j;
int pv;
int tmp;
bool flag0, flag;

i = L;
j = R;

pv = x.list[(L + R)/2];

flag0 = true;
#pragma hls_unroll yes
for(int k=0; k<4; k++){ // len(x.list) = 4

  flag = true;
  #pragma hls_unroll yes
  for(int ki=0; ki<4; ki++){ 
	if(x.list[i] < pv)
	  flag = false;
	
	if(flag)
		i++;
  }
  
  flag = true;
  #pragma hls_unroll yes
  for(int kj=0; kj<4; kj++){
	if(pv < x.list[j])
	  flag = true;
	
	if(flag)
		j--;
  }
  
  if(i>=j)
	  flag0 = false;
  
  if(flag0){
	  tmp = x.list[i];
	  x.list[i] = x.list[j];
	  x.list[j] = tmp;
	  
	  i++;
	  j--;
  }

}

/*
if(L < i-1)
process(x, L, i-1);

if(j+1 < R)
process(x, j+1, R);
*/

return x;
}

-- end of code ---

from fully-homomorphic-encryption.

After talking with the XLS team they agreed the solver was struggling to prove the loops unroll, but what I learned is that it wasn't that it's hard to prove they unroll, but that it's hard for the solver to find the minimal unrolling, which is what it does. The nested breaks inside of if statements apparently make this difficult.

As a workaround, they added this [new parameter to xlscc] (google/xls@500af15) that allows one to set an effective time limit on the loop unrolling solver, and a quick test shows that it causes the compilation to succeed.

I have to integrate this flag into the project so that it is passed to xlscc by default and configurable by the user, which should be done this week.

from fully-homomorphic-encryption.

Thank you for your message and management. I will wait for that integration.

from fully-homomorphic-encryption.

The fix is in review. However, I did notice that, even though it compiles, with the recursive calls included the resulting circuit has some 600,000 gates. I would expect such a program to take maybe 24h to run, which may be an issue for you.

from fully-homomorphic-encryption.

Thank you for the notification.
The huge circuit is no problem but important information. I want to know how coding structures effect on the efficiency of FHE computations.

from fully-homomorphic-encryption.

The fix is taking a bit longer than expected, because upgrading the version of XLS to get this new parameter resulted in some unrelated build errors that required some project reconfiguration. A patch is in the works and I hope it will be through today or tomorrow.

from fully-homomorphic-encryption.

This commit should fix the issue c3df97c

from fully-homomorphic-encryption.

Thank you very much for your work of the fixing.
I will try it.

from fully-homomorphic-encryption.