6/11    Anybody know if encryption routines (DES, IPsec related, etc) can
        be parallelized?  Does adding more CPUs and writing some parallel
        software speed things up?
        \_ Look at the source code.  Much of the time, what can be
           parallelized is done at a fine grain level (vector data,
           level, loop level, instruction level, etc...) in which
           case, adding CPU's won't do you any good.  If it's thread
           level paralellism, then yes.  Go to http://mit.edu's web site and
           search for Krste Asonovic (he was a PhD student here w/
           Patterson).  His thesis has a good explaination.  Also look
           at the spring 2000 cs252 website.  I think someone did
           a project on encryption algorithms. -jeff
        \_ IPSEC isn't an encryption routine--IPSEC ESP just makes
           provision for tunnel encryption and key exchange for
           whatever crypto you're using.  -John the Nitpicker
        \_ No.
        \_ It depends on the feedback mode used.  If the cyper is running
           in ECB mode, yes, but it's a bad mode of operation otherwise.
           the most common mode, CFB mode, has a dependency between
           blocks and can't be parallelized.  -nweaver
           \_ is that a mathematically proven statement or a "can't _easily_
              be paralellized"?
                \_ Do you understand what you're talking about?  If step B
                   depends on the result of step A before it can be started,
                   IT'S IMPOSSIBLE TO RUN A & B IN PARALLEL.
                   \_ Do YOU understand what YOU are talking about? There's
                      more than one way to split a task into blocks, and
                      parallelism need not apply at global level to be useful.
                      A complete mathematical proof of nweaver's statement
                      would be quite difficult.
                   \_ Not so.  It's been done before in superscalar
                      processors using load value prediction and
                      trivial computation predictions.
                   \_ CFB can not be parallelized beyond the parallelism
                      inherant in the encryption of a single block, because
                      of the dependency.  CFB of block N is computed by
                      encrypting the value of N xor the last block.  -nweaver
                      \_ look, computation prediction is NOT trivial!!
                   \_ CFB encyption can NOT be parallelized beyond the
                      parallelimsm inherant in the encryption of a single
                      block, because of the cyclic dependency.  You need to
                      completely encrypt one block before you can begin
                      encrypting the next block.  CFB DECRYPTION however,
                      can be parallelized between blocks.  -nweaver