It is believed that optimal workload allocation cannot be achieved without considering the cost of parallelism in a given environment. This paper presents a machine learning approach to allocate parallel workload in a cost-aware manner. This instance-based learning approach uses static program features to classify programs, before deciding the best workload allocation scheme based on its prior experience with similar programs. Experimental results on 76 Java benchmarks show that it can find the optimal workload allocation schemes for 36 out of them and over 85% of the best speedups on the other 19. It shows that this approach can efficiently allocate parallel workload among Java threads and achieve optimal or suboptimal performance.