Today, VLSI design involves millions of components, the performance of which is sensitive to design time decisions. CAD software --- which must be both computationally fast, and able to produce near optimal solutions --- is used to handle the growing complexity of VLSI design. Utilizing modern commodity hardware, this Thesis empirically examines parallel methods for finding solutions to the VLSI Circuit Partitioning problem. We combine parallel methods with the Fidducia-Mattheyses, Memetic Algorithm, and Scatter Search advanced search techniques to find near optimal solutions in a reasonable amount of time. We examine a total nine algorithms, three sequential, and six parallel, to determine their effect on solution quality, and runtime. We developed both a Memetic Algorithm, and a Scatter Search algorithm for this investigation, and utilized two parallelization techniques, a Master-Slave design and a Multi-Walk design which implements migration. Experimental results indicate that our parallel techniques give competitive results that are suitable for VLSI design.