Первый шаг, который вы должны сделать, - это очевидный шаг: оберните внешний цикл в параллель для директивы. Как вы предполагаете. Всегда стоит немного поэкспериментировать, чтобы получить доказательства, подтверждающие ваши (и мои) предположения, но если бы вам было позволено сделать только 1 изменение, которое будет сделано.
Я не знаю много о алгоритмах, не обращающих внимания на кэш, но я понимаю, что они, как правило, работают путем рекурсивного разделения проблемы на подзадачи. Это, кажется, не соответствует применению параллели для директив. Я подозреваю, что вы могли бы реализовать такой алгоритм с задачами OpenMP, но я подозреваю, что затраты на это перевесят любые улучшения выполнения любого m-v продукта разумных размеров.
(Если вы продемонстрируете ложность этого аргумента на m-v продуктах размера N, я отвечу «N не является разумным измерением». Как и всегда, с этими вопросами производительности, доказательство всегда опровергает аргумент.)
Наконец, в зависимости от вашего компилятора и доступности библиотек, вам может не потребоваться использовать OpenMP для вычислений mv, вы можете обнаружить, что автоматическое распараллеливание работает эффективно, или уже есть реализация библиотеки, которая использует многопоточность такого рода вычислений.