OpenMP はひとまとまりの大きなデータ（行列とか画像とか）に対する計算を
複数のスレッドで並列化するのに向いている希ガス。つまりデータ並列向き。
データ並列性のある for 文で書かれたアルゴリズム（行列ベクトル積とか
画像のしきい値処理とか）は parallel for ディレクティブでいとも簡単に並列化できる。
そこが OpenMP のおいしいところ。

タスク並列の並列プログラム、つまり各スレッドが独立に違う処理をする
（例えばそれぞれ別のクライアントからの要求を処理する）並列プログラムも
OpenMP で書けるけど、あまりうまみがないと思われ。

逐次プログラムを並列化するのが前提というのは違う気がする。
ただ、例えば parallel for ディレクティブしか使ってない並列プログラムは
コンパイラの OpenMP 機能をオフにすれば逐次プログラムとしてコンパイルできる。
そこが他の並列化手法（POSIXスレッドとかMPIとか）と違うところ。

でも、OpenMP機能をオフにするとコンパイル不能になる並列プログラムも書けるし、
parallel sections を使ったプログラムは逐次プログラムとしてコンパイルはできても
意味が変わってしまう（各セクションが順番に逐次実行される）。
つまり、この手のプログラムは並列で動くことが前提で書くわけだ。

結局のところ、OpenMP を使うのが妥当かどうかは126さんがやりたいことに依る。
並列性の高いデータ並列の計算をやりたいなら使う価値がある。