Trong phạm vi luận văn này trình bày ba phần chính. Chương 1 trình bày tổng quan về xử lý song song, thuật toán song song và giới thiệu lập trình song song với MPI. Chương 2 trình bày về phương pháp thiết kế thuật toán tìm dãy con chung dài nhất trong tính toán song song. Chương 3 trình bày một số kết quả thực nghiệm trên dữ liệu cho chương trình song song tìm dãy con chung dài nhất. | Xét về thời gian chạy, trên bảng , khí số xâu ký tự bằng 2 với độ dài 64 trên bảng chứ cái 4 ký tự cho thấy thời gian thực hiện thuật toán tuần tự rất ngắn, bằng giây. Thuật toán song song với số bộ xử lý càng tăng thì thời gian tính toán càng chậm lần lượt bằng , , với 2, 4 và 8 bộ xử lý. Đặc biệt khi số xâu tăng lên bằng 4, thời gian tính toán tuần tự mất giây so với giây của thuật toán song song với 2 bộ xử lý, giây với 4 bộ xử lý và giây với 8 bộ xử lý. Có thể nhận thấy trong trường hợp này, thuật toán tuần tự nhanh hơn so với thuật toán song song bởi số lượng tính toán không nhiều, các thuật toán song song mất thời gian truyền thông giữa các bộ xử lý. Khi thời gian tính toán thấp hơn rất nhiều so với thời gian truyền thông thì các thuật toán song song không hiệu quả. Khi các tính toán đủ lớn, mất thời gian khá nhiều như trường hợp với 8 xâu, thuật toán song song tỏ ra có ưu thế hơn hẳn. Thời gian thực hiện thuật toán giảm dần từ giây đối với thuật toán tuần tự chỉ còn 15
