Numpy einsum_path сообщает больше FLOP и «ускорение» - PullRequest
Новая
       16

Numpy einsum_path сообщает больше FLOP и «ускорение»

0 голосов
/ 07 ноября 2018

По теме np.einsum я уже прочитал кучу обсуждений по адресу:

Чтобы понять, почему np.eimsum быстрее, чем обычно np.sum, np.product и т. Д. (Даже для последней версии NacPy в Anaconda), я использую np.einsum_path, чтобы увидеть, что сделал оптимизация процесса оптимизации.

При этом я обнаружил интересное явление. Рассмотрим этот минимальный пример: 

import numpy as np
for i in 'int8 int16 int32 int64 uint8 uint16 uint32 uint64 float32 float64'.split():
    print(np.einsum_path('i->', np.empty(2**30, i))[1])

Выходы все идентичны: 

  Complete contraction:  i->
         Naive scaling:  1
     Optimized scaling:  1
      Naive FLOP count:  1.074e+09
  Optimized FLOP count:  2.147e+09
   Theoretical speedup:  0.500
  Largest intermediate:  1.000e+00 elements
--------------------------------------------------------------------------
scaling                  current                                remaining
--------------------------------------------------------------------------
   1                         i->                                       ->

Где Optimized FLOP увеличивается (что означает больше вычислений?) И Теоретическое ускорение меньше 1 (что означает медленнее). Но если мы действительно рассчитаем время: 

for i in 'int8 int16 int32 int64 uint8 uint16 uint32 uint64 float32 float64'.split():
    a    = np.empty(2**27, i)
    raw  = %timeit -qon9 a.sum()
    noOp = %timeit -qon9 np.einsum('i->', a, optimize=False)
    op   = %timeit -qon9 np.einsum('i->', a, optimize='greedy')
    print(i, raw.average/op.average, noOp.average/op.average, sep='\t')

Если мы посмотрим на второй столбец, соответствующий «собственному» времени, разделенному на оптимизированное время, все они близки к 1, что означает, что оптимизация не сделала его медленнее: 

int8    4.485133392283354   1.0205873691331475
int16   3.7817373109729213  0.9528030137222752
int32   1.3760725925789292  1.0741615462167338
int64   1.0793509548186524  1.0076602576129605
uint8   4.509893894635594   0.997277624256872
uint16  3.964949791428885   0.9914991211913878
uint32  1.3054813163356085  1.009475242303559
uint64  1.0747670688044795  1.0082522386805526
float32 2.4105510701565636  0.9998241152368149
float64 2.1957241421227556  0.9836838487664662

Мне интересно, будет ли рана np.einsum_path говорить, что она требует больше FLOP и медленнее? Я считаю, что время вычисляется напрямую из числа FLOP, поэтому эти два теста в основном относятся к одному и тому же.

Кстати, я прилагаю пример, показывающий, как np.einsum_path "обычно" ведет себя, чтобы убедить приведенный выше результат в ненормальном: 

a = np.empty((64, 64))
print(np.einsum_path('ij,jk,kl->il', a, a, a)[1])
noOp = %timeit -qon99 np.einsum('ij,jk,kl->il', a, a, a, optimize=False)
op   = %timeit -qon99 np.einsum('ij,jk,kl->il', a, a, a, optimize='greedy')
print('Actual speedup:', noOp.average / op.average)

который выводит: 

  Complete contraction:  ij,jk,kl->il
         Naive scaling:  4
     Optimized scaling:  3
      Naive FLOP count:  5.033e+07
  Optimized FLOP count:  1.049e+06
   Theoretical speedup:  48.000
  Largest intermediate:  4.096e+03 elements
--------------------------------------------------------------------------
scaling                  current                                remaining
--------------------------------------------------------------------------
   3                   jk,ij->ik                                kl,ik->il
   3                   ik,kl->il                                   il->il
Actual speed up: 90.33518444642904

1 Ответ

0 голосов
/ 07 ноября 2018

Я только что копался в исходном коде np.einsum_path. Согласно комментарию здесь (т.е. здесь ): 

# Compute naive cost
# This isn't quite right, need to look into exactly how einsum does this

и способ вычисления оптимальной стоимости (т. Е. здесь , не проводите слишком долго). Кажется, что способ, которым вычисляются две затраты, является непоследовательным, в то время как первая документально подтверждена как «не совсем правильная».

Затем я распечатал «нативный» (т.е. не оптимизированный) einsum_path: 

import numpy as np
print(np.einsum_path('i->', np.empty(2**30, 'b'), optimize=False)[1])

что удивительно "отличается от родного": 

  Complete contraction:  i->
         Naive scaling:  1
     Optimized scaling:  1
      Naive FLOP count:  1.074e+09
  Optimized FLOP count:  2.147e+09
   Theoretical speedup:  0.500
  Largest intermediate:  1.000e+00 elements
--------------------------------------------------------------------------
scaling                  current                                remaining
--------------------------------------------------------------------------
   1                         i->                                       ->

Таким образом, причиной сообщаемого снижения скорости является просто ошибка подсчета флопа. np.einsum фактически не выполнял никакой оптимизации path (хотя по какой-то причине он все еще существенно быстрее, чем собственный np.sum).

...