{"action":"created","issue":{"url":"https://api.github.com/repos/tfhe/tfhe/issues/182","repository_url":"https://api.github.com/repos/tfhe/tfhe","labels_url":"https://api.github.com/repos/tfhe/tfhe/issues/182/labels{/name}","comments_url":"https://api.github.com/repos/tfhe/tfhe/issues/182/comments","events_url":"https://api.github.com/repos/tfhe/tfhe/issues/182/events","html_url":"https://github.com/tfhe/tfhe/issues/182","id":374806062,"node_id":"MDU6SXNzdWUzNzQ4MDYwNjI=","number":182,"title":"[v1] Possible FFT optimizations?","user":{"login":"CapacitorSet","id":9286933,"node_id":"MDQ6VXNlcjkyODY5MzM=","avatar_url":"https://avatars1.githubusercontent.com/u/9286933?v=4","gravatar_id":"","url":"https://api.github.com/users/CapacitorSet","html_url":"https://github.com/CapacitorSet","followers_url":"https://api.github.com/users/CapacitorSet/followers","following_url":"https://api.github.com/users/CapacitorSet/following{/other_user}","gists_url":"https://api.github.com/users/CapacitorSet/gists{/gist_id}","starred_url":"https://api.github.com/users/CapacitorSet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CapacitorSet/subscriptions","organizations_url":"https://api.github.com/users/CapacitorSet/orgs","repos_url":"https://api.github.com/users/CapacitorSet/repos","events_url":"https://api.github.com/users/CapacitorSet/events{/privacy}","received_events_url":"https://api.github.com/users/CapacitorSet/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-10-28T22:27:25Z","updated_at":"2018-11-01T12:33:04Z","closed_at":null,"author_association":"NONE","body":"I was reviewing [the FMA FFT loop](https://github.com/tfhe/tfhe/blob/v1.0.1/src/libtfhe/fft_processors/spqlios/spqlios-fft-fma.s#L79):\r\n\r\n```asm\r\nfftsize2loop:\r\n\tvmovapd (%r10),%ymm0 /* r0 r1 r2 r3 */\r\n\tvmovapd (%r11),%ymm1 /* i0 i1 i2 i3 */\r\n\tvshufpd $0,%ymm0,%ymm0,%ymm2  /* r0 r0 r2 r2 */\r\n\tvshufpd $15,%ymm0,%ymm0,%ymm3 /* r1 r1 r3 r3 */\r\n\tvshufpd $0,%ymm1,%ymm1,%ymm4  /* i0 i0 i2 i2 */\r\n\tvshufpd $15,%ymm1,%ymm1,%ymm5 /* i1 i1 i3 i3 */\r\n\tvfmadd231pd %ymm3,%ymm12,%ymm2 /* (r0 r0 r2 r2) + (r1 -r1 r3 -r3) */\r\n\tvfmadd231pd %ymm5,%ymm12,%ymm4 /* (i0 i0 i2 i2) + (i1 -i1 i3 -i3) */\r\n\tvmovapd %ymm2,(%r10)\r\n\tvmovapd %ymm4,(%r11)\r\n\t/* end of loop */\r\n        leaq 32(%r10),%r10\r\n        leaq 32(%r11),%r11\r\n        addq $4,%rax\r\n\tcmpq %r9,%rax\r\n\tjb fftsize2loop\r\n```\r\n\r\nI noticed a few possible optimizations that would result in simpler code, and possibly fewer instructions, but I can't apply them because they change the data layout in registers and I'm not skilled enough in assembly programming to refactor the surrounding code.\r\n\r\n * `ymm12 = (+1.0 -1.0 +1.0 -1.0)` is used to alternate signs. This can be done natively by [`addsubpd`](https://www.felixcloutier.com/x86/ADDSUBPD.html), which doesn't require FMA. Indeed, if vfmadd were replaced with addsub, there would be only two FMA instructions left (in `.fftoffloop`) in what seems like a cold area, which could lead to dropping FMA-specific code. However, using `addsubpd` is equivalent to multiplying by `(-r1 r1 -r3 r3)` (i.e. with signs flipped), which is not compatible with the rest of the code. One could simply XOR `ymm2` with `-0.0`, but I'd rather not add another instruction in a tight loop.\r\n * The 2 FMA instructions perform 8 FMAs, but they are really 4 products with signs flipped. Perhaps it would be faster if it were a simple AVX multiplication  and sign flip - but again, this would change the data layout, and I can't refactor the code.\r\n\r\nCheers!"},"comment":{"url":"https://api.github.com/repos/tfhe/tfhe/issues/comments/435026630","html_url":"https://github.com/tfhe/tfhe/issues/182#issuecomment-435026630","issue_url":"https://api.github.com/repos/tfhe/tfhe/issues/182","id":435026630,"node_id":"MDEyOklzc3VlQ29tbWVudDQzNTAyNjYzMA==","user":{"login":"ngama75","id":8881519,"node_id":"MDQ6VXNlcjg4ODE1MTk=","avatar_url":"https://avatars3.githubusercontent.com/u/8881519?v=4","gravatar_id":"","url":"https://api.github.com/users/ngama75","html_url":"https://github.com/ngama75","followers_url":"https://api.github.com/users/ngama75/followers","following_url":"https://api.github.com/users/ngama75/following{/other_user}","gists_url":"https://api.github.com/users/ngama75/gists{/gist_id}","starred_url":"https://api.github.com/users/ngama75/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ngama75/subscriptions","organizations_url":"https://api.github.com/users/ngama75/orgs","repos_url":"https://api.github.com/users/ngama75/repos","events_url":"https://api.github.com/users/ngama75/events{/privacy}","received_events_url":"https://api.github.com/users/ngama75/received_events","type":"User","site_admin":false},"created_at":"2018-11-01T12:33:04Z","updated_at":"2018-11-01T12:33:04Z","author_association":"CONTRIBUTOR","body":"you're right!\r\n\r\nChanging the layout will be indeed complex, \r\nbut it would be worth to test the solution where we flip the all sign bits with a VXORPD instruction.\r\nIndeed, addsubpd + vxorpd may indeed be quicker than vfmadd.\r\n\r\nDo you want to test it in a branch?\r\n\r\nCheers,"}}
{"actor":{"display_login":"ngama75"}}