Я думаю тут рано переходить на использование регистров. У вас чтение выражения из памяти в EvaluateTestCase не coaslesced, значит на порядок медленнее, чем могло бы быть. Для контроля достигнутой скорости доступа к памяти посчитайте общее количество байт ваш кернел читает и пишет в память, и поделите на общее время исполнения. Получится какая-то скорость в ГБ/c. Она должна быть близка к пиковой пропускной способности, обычно 80-90% пропускной способности шины (12.8ГБ/с на 8500GT). У вас будет гораздо меньше --- есть над чем работать.

Другое узкое место --- вы читаете одни и те же данные в соседних тредах независимо, то есть потребляете на один или несколько порядков больше пропускной способности памяти, чем надо. Одно решение: читать выражение через кеш (текстурную память, лучше линейную, 1D). Недостаток: у кэша большая задержка, несколько сот циклов. Другое решение: прочитать сначала выражение в shared memory, потом уже читать оттуда из разных тредов. В этом случае надо будет убедиться, что все треды одного блока работают с одним выражением. Можно использовать паддинг если это не так.

После того, как доступ в память эффективно организован и производительности ограничена пропускной способностью исполнения инструкций, будет имеет смысл оптимизировать доступ к shared memory и регистрам.