Recently, cluster computing has successfully provided a cost-effective solution for data-intensive applications. In order to make the programming on clusters easy, many programming toolkits such as MPICH, PVM, and DSM have been proposed in past researches. However, these programming toolkits are not easy enough for common users to develop parallel applications. To address this problem, we have successfully implemented the OpenMP programming interface on a software distributed shared memory system called Teamster. On the other hand, we add a scheduling option called Profiled Multiprocessor Scheduling (PMS) into the OpenMP directive. When this option is selected in user programs, a load balance mechanism based on the PMS algorithm will be performed during the execution of the programs. This mechanism can automatically balance the workload among the execution nodes even when the CPU speed and the processor number of each node are not identical. In this paper, we will present the design and implementation of the OpenMP API on Teamster, and discuss the results of performance evaluation in the test bed.