自90年代以来,为了适应计算在科学研究和实际应用中求解大规模问题和复杂系统的要求,高性能并行计算得以空前飞速发展。但随着超级计算机规模的不断扩大,并行算法的可扩展性研究日益得到重视。针对这种应用需求,本文对平面Delaunay三角剖分（DT）的传统高性能计算,以及SAT和精确覆盖两个经典NP完全问题的非传统高性能计算中的可扩展并行计算问题展开了研究。首先,对于Delaunay三角剖分问题,目前已出现了不少成熟的算法,但这些算法各有优劣。本文结合逐点插入法和分治法,并引入著名的投影法和凸壳技术,提出了两个DT并行算法。其中一个算法基于PRAM-EREW计算模型,在不增加总操作数复杂度的前提下,将时间复杂度减小到O（n）。算法虽然获得了较好的时间性能,却没有考虑可扩展性。因此,本文同时提出一个基于PRAM-CREW计算模型的具有较好可扩展性的并行DT算法,新算法在保持总操作数O（nlogn）不变的情况下,时间性能可随处理器个数的增加而提高。对于NP完全问题,传统高性能计算依然不能解决计算时间或处理机个数呈指数增加的问题。DNA计算以其海量存储和并行运算能力,被认为是解决NP完全问题和其它难解问题的潜在方案之一。但是,目前DNA计算中依然存在类似传统高性能计算问题中的“指数爆炸”问题。针对这一现象,本文提出一种具有良好可扩展性的DNA计算机新模型,并将其成功应用于求解精确覆盖问题的DNA计算机算法,新算法在保持原有多项式时间复杂度的前提下,将所需的DNA链数从O（2ⁿ）降低到O(2^n/2)。此外,基于Chang模型,本文同时提出了求解SAT问题的DNA算法,该算法摒弃了传统的解穷举方式,无需构造初始解空间,从而使得新算法能够在多项式时间的前提下,根据实际情况有效地减少所需DNA链数和链长。