заменить не-coalesced чтение на чтение из текстуры вовсе не сложно. Надо только привязать текстуру, скажем tExpressions, к участку памяти где хранятся выражения --- cudaBindTexture(0, tExpressions, pExpressions, size), и вместо pExpressions[index] писать tex1Dfetch(tExpressions,index). Я думаю одно это может дать сильный прирост, поскольку устраняет не-coalesced доступ и снижат нагрузку на шину памяти.

А зачем вы запускаете максимальное количество потоков на блок? И сколько это получается? Какова максимальная глубина стека?