Luận án tiến sĩ Predictive Adaptive Parallelism của David L. Wangerin
Luận án tiến sĩ về song song thích ứng dự đoán. Đề xuất phương pháp tối ưu hiệu suất máy tính đa xử lý qua dự đoán động và phân chia công việc thích ứng.
University of California, Irvine
Information and Computer Science
Luan An
Luận án
Năm xuất bản
Số trang
145
Thời gian đọc
22 phút
Lượt xem
1
Lượt tải
0
Phí lưu trữ
40 Point
Tổng quan nhanh
- Chủ đề:
- 1. Predictive Adaptive Parallelism Overview
- Số trang:
- 145 trang
- Trường:
- University of California, Irvine
- Chuyên ngành:
- Information and Computer Science
- Tác giả:
- David L. Wangerin
- Năm:
- 2006
Tóm tắt nội dung luận án
I. Predictive Adaptive Parallelism Overview
Predictive Adaptive Parallelism represents a groundbreaking approach to parallel computing optimization. The dissertation introduces novel techniques for dynamic workload prediction and runtime adaptation. Traditional parallel computing systems struggle with irregular workloads and varying data characteristics. This research addresses these limitations through machine learning prediction and adaptive algorithms.
The core innovation lies in performance vector analysis. Load vectors capture computational characteristics across different program segments. These vectors enable intelligent thread management decisions at runtime. The system adapts to changing conditions without manual intervention.
Computational efficiency improves significantly through predictive scheduling. The framework analyzes instruction classes and execution patterns. Dynamic scheduling algorithms adjust resource allocation based on real-time performance data. This adaptive approach outperforms static compilation techniques.
The research demonstrates practical applications across multiple domains. Benchmark testing validates the theoretical framework. Results show substantial performance gains on heterogeneous systems. Load balancing becomes more effective through continuous monitoring and adjustment.
1.1. Core Research Problem
Parallel programs face irregularity challenges from data set variations. Performance degradation occurs when workloads deviate from expected patterns. Static compiler optimizations cannot address runtime variations. The dissertation identifies three primary sources of irregularity: data set size variations, data value dependencies, and dynamic program behavior. These factors prevent optimal resource utilization in traditional parallel computing frameworks.
1.2. Proposed Solution Framework
The Predictive Adaptive Parallelism system combines workload prediction with runtime adaptation. Performance vectors quantify computational requirements across program segments. Load vectors track instruction class distributions and execution characteristics. The framework enables dynamic thread allocation based on predicted workloads. Machine learning prediction models forecast execution patterns from historical data.
1.3. Key Innovation Areas
Three major innovations distinguish this research. First, performance vector methodology provides fine-grained workload characterization. Second, adaptive algorithms adjust parallelization strategies during execution. Third, predictive models anticipate resource requirements before execution begins. These components work synergistically to optimize computational efficiency across diverse workload conditions.
II. Performance Vector Analysis Methods
Performance vectors form the foundation of predictive adaptive parallelism. These mathematical constructs capture program execution characteristics. Each vector represents computational workload across defined instruction classes. The methodology enables quantitative comparison between program segments.
Load vector generation occurs through static program analysis. The system examines basic blocks and control flow structures. Instruction counting produces initial workload estimates. Loop structures receive special treatment for variant identification.
Vector composition includes multiple instruction classes. Memory operations, arithmetic computations, and control flow instructions each contribute. The granularity of classification affects prediction accuracy. Finer classifications improve precision but increase overhead.
Predictive models use historical vector data. Machine learning algorithms identify patterns across executions. The system forecasts future workloads based on input characteristics. Accuracy improves through continuous learning and refinement.
Runtime adaptation leverages real-time vector updates. Actual execution data refines initial predictions. The framework adjusts thread allocation dynamically. This feedback loop ensures optimal resource utilization throughout program execution.
2.1. Load Vector Construction
Load vectors quantify computational requirements for program segments. Static analysis examines source code structure and instruction sequences. The system categorizes instructions into predefined classes based on operation type. Each class receives a weight reflecting execution cost. Vector components represent expected instruction counts per class. This representation enables mathematical comparison between different parallelization strategies.
2.2. Instruction Classification System
The framework defines distinct instruction classes for accurate workload modeling. Categories include integer arithmetic, floating-point operations, memory accesses, and control flow instructions. Each class exhibits different performance characteristics on target hardware. Classification granularity balances prediction accuracy against computational overhead. The appendix details complete instruction class definitions and associated cost metrics.
2.3. Vector Based Prediction Models
Predictive algorithms transform load vectors into execution time estimates. Machine learning models correlate vector characteristics with observed performance. Training data comes from previous program executions across varying inputs. The system identifies relationships between vector components and runtime behavior. Prediction accuracy determines the effectiveness of adaptive scheduling decisions.
III. Dynamic Scheduling Adaptive Algorithms
Dynamic scheduling algorithms form the execution engine for adaptive parallelism. These algorithms make real-time decisions about thread allocation. The system balances computational load across available processors. Optimization goals include minimizing total execution time and maximizing resource utilization.
The framework supports multiple parallelism patterns. Loop level parallelism distributes iteration spaces across threads. Task level parallelism assigns independent operations to separate processors. Pipeline parallelism streams data through sequential processing stages.
Load balancing strategies adapt to workload characteristics. Homogeneous systems use equal distribution strategies. Heterogeneous systems require capability-aware allocation. The scheduler considers processor speeds and memory hierarchies.
Thread management overhead requires careful consideration. Thread creation and synchronization impose costs. The system balances parallelism benefits against coordination overhead. Adaptive algorithms adjust thread counts based on workload granularity.
Runtime adaptation responds to prediction errors. Monitoring systems detect performance deviations. The framework reallocates resources when actual workloads differ from predictions. This self-correction mechanism maintains efficiency despite imperfect forecasting.
3.1. Loop Level Parallelism Optimization
Loop parallelization represents the most common parallel computing pattern. The system analyzes loop variants to predict iteration workloads. Regular loops with constant iteration costs use simple division strategies. Irregular loops require sophisticated prediction based on data characteristics. The scheduler determines optimal iteration distribution across available threads. Performance optimization considers both computation and communication costs.
3.2. Task Level Parallelism Management
Task parallelism assigns independent program segments to separate processors. The framework identifies parallelizable tasks through dependency analysis. Performance vectors estimate computational requirements for each task. Dynamic scheduling allocates tasks based on processor availability and capability. Load balancing ensures no processor remains idle while work remains. The system handles both embarrassingly parallel and loosely coupled task structures.
3.3. Heterogeneous System Adaptation
Heterogeneous computing environments present unique scheduling challenges. Processors vary in speed, memory capacity, and architectural features. The adaptive framework characterizes each processor's capabilities. Workload distribution accounts for performance differences across resources. Capability-aware scheduling assigns larger workloads to faster processors. This approach maximizes overall system throughput on diverse hardware configurations.
IV. Runtime Adaptation Thread Management
Runtime adaptation enables continuous performance optimization during execution. The system monitors actual performance against predictions. Deviations trigger adaptive responses to maintain efficiency. This dynamic approach handles unpredictable workload variations.
Thread count adjustment represents a primary adaptation mechanism. The framework increases parallelism when workloads exceed predictions. Thread reduction occurs when overhead exceeds parallelism benefits. Adaptation decisions consider current system state and workload characteristics.
Communication pattern optimization reduces synchronization overhead. The system identifies communication bottlenecks through runtime monitoring. Adaptive algorithms restructure data exchange patterns. This optimization improves performance in communication-intensive applications.
Nested parallelism presents complex management challenges. Multiple parallel regions may execute simultaneously. The framework coordinates resource allocation across nesting levels. Hierarchical scheduling prevents resource contention between nested regions.
Performance feedback loops enable continuous improvement. Actual execution data updates predictive models. Machine learning algorithms refine predictions based on observed behavior. This learning process increases accuracy over repeated executions.
4.1. Real Time Performance Monitoring
Continuous monitoring tracks actual execution characteristics during runtime. The system measures instruction execution rates and memory access patterns. Performance counters provide hardware-level execution data. Monitoring overhead must remain minimal to avoid degrading overall performance. Collected data feeds into adaptive decision-making algorithms. Real-time analysis enables rapid response to changing workload conditions.
4.2. Adaptive Thread Allocation Strategies
Thread allocation adapts based on observed performance and predicted workloads. The framework adjusts thread counts to match computational requirements. Increasing threads improves parallelism for large workloads. Decreasing threads reduces overhead for fine-grained operations. Allocation decisions consider thread creation costs and synchronization overhead. The system finds optimal thread counts through iterative refinement.
4.3. Communication Overhead Reduction
Communication costs often dominate parallel program performance. The adaptive framework minimizes data transfer between threads. Scheduling algorithms co-locate communicating tasks when possible. Data replication strategies reduce remote memory access frequency. The system balances communication reduction against load balancing requirements. Network topology awareness improves performance on distributed systems.
V. Workload Prediction Machine Learning
Machine learning prediction enhances adaptive parallelism effectiveness. Predictive models forecast execution characteristics from program inputs. Training data comes from historical execution profiles. Model accuracy directly impacts scheduling quality.
Feature extraction identifies relevant input characteristics. Data set size represents an obvious predictive feature. Data value distributions affect execution paths in conditional code. Input complexity metrics correlate with computational requirements.
Model selection balances accuracy against computational cost. Simple linear models provide fast predictions with limited accuracy. Neural networks achieve higher accuracy but require more computation. The framework chooses models appropriate for application characteristics.
Training strategies determine model quality. Offline training uses historical execution data. Online learning adapts models during program execution. Hybrid approaches combine both strategies for optimal results.
Prediction confidence metrics guide adaptive decisions. High-confidence predictions enable aggressive optimization. Low-confidence scenarios trigger conservative strategies. The system adjusts risk tolerance based on prediction quality.
5.1. Feature Engineering for Prediction
Effective prediction requires identifying relevant input features. Data set dimensions provide primary predictive information. Value distributions indicate computational complexity for data-dependent algorithms. Historical execution patterns reveal recurring workload characteristics. Feature selection reduces dimensionality while preserving predictive power. The system automatically identifies salient features through correlation analysis.
5.2. Model Training and Validation
Training processes establish relationships between features and execution characteristics. Supervised learning uses labeled execution data from benchmark runs. Cross-validation ensures model generalization across diverse inputs. The framework partitions training data to prevent overfitting. Validation metrics assess prediction accuracy on unseen data. Continuous retraining maintains model relevance as workload patterns evolve.
5.3. Online Learning Adaptation
Online learning enables model refinement during production execution. The system updates predictions based on observed performance. Incremental learning algorithms incorporate new data without complete retraining. This approach handles workload drift and changing system conditions. Learning rates balance stability against adaptation speed. Online adaptation improves prediction accuracy for evolving application behaviors.
VI. Experimental Results Performance Analysis
Comprehensive experimental validation demonstrates framework effectiveness. Testing covers diverse applications and system configurations. Results show significant performance improvements over static approaches. The Jacobi relaxation algorithm serves as primary benchmark.
Benchmark selection represents various parallel computing patterns. Loop-intensive scientific computations test iteration distribution. Task-parallel applications validate independent workload scheduling. Pipeline applications assess streaming data processing optimization.
System configurations include homogeneous and heterogeneous platforms. Testing spans different processor counts and network topologies. Performance varies based on workload characteristics and system capabilities. Adaptive approaches show greatest benefits on heterogeneous systems.
Performance metrics quantify optimization effectiveness. Speedup measurements compare parallel versus sequential execution. Efficiency metrics assess resource utilization quality. Scalability analysis examines performance across processor counts.
Timing results validate predictive accuracy. Predicted execution times closely match observed performance. Adaptation overhead remains minimal compared to performance gains. The framework achieves near-optimal scheduling in most scenarios tested.
6.1. Jacobi Relaxation Benchmark Results
The Jacobi relaxation algorithm provides comprehensive performance testing. Experiments vary matrix dimensions from 32 to 1024 elements. Iteration counts range from single to multiple passes. Results demonstrate effective load balancing across thread counts. Timing plots show performance optimization across system configurations. The adaptive framework consistently outperforms static thread allocation strategies.
6.2. Heterogeneous System Performance
Heterogeneous platforms reveal adaptive scheduling advantages. Processor speed variations create load balancing challenges. The framework successfully distributes workload proportional to capabilities. Performance gains increase with greater system heterogeneity. Capability-aware scheduling prevents fast processors from waiting idle. Results validate the effectiveness of performance vector-based workload estimation.
6.3. Scalability and Overhead Analysis
Scalability testing examines performance across processor counts. The framework maintains efficiency as thread counts increase. Prediction overhead remains below five percent of total execution time. Adaptation costs decrease relative to benefits for larger workloads. Communication overhead grows with processor count but remains manageable. The system demonstrates good scalability characteristics for tested applications.
Mục lục chi tiết luận án
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (145 trang)Nội dung chính
Tổng quan về luận án
Luận án của David L. Wangerin, "Predictive Adaptive Parallelism," xuất hiện trong bối cảnh khoa học tính toán song song đang phát triển mạnh mẽ. Trong những thập kỷ gần đây, chi phí máy trạm và thiết bị mạng giảm liên tục trong khi hiệu suất tăng đáng kể, biến tính toán song song từ một lĩnh vực chuyên biệt thành một công cụ dễ tiếp cận và hiệu quả hơn. Tuy nhiên, cùng với sự tăng trưởng này là thách thức cố hữu: mặc dù việc sử dụng nhiều tài nguyên xử lý có khả năng tăng tốc độ thực thi chương trình, nhưng trên thực tế, tốc độ tăng tuyến tính hiếm khi đạt được do chi phí vận hành tăng lên theo số lượng tài nguyên bổ sung.
Tính tiên phong của nghiên cứu này nằm ở việc đề xuất một phương pháp tiếp cận mới mẻ để tự động tối ưu hóa các chương trình song song, khắc phục những hạn chế đáng kể của các phương pháp hiện hành. Luận án đặt ra mục tiêu "tự động tính toán số lượng luồng tối ưu cho các chương trình song song tại thời điểm chạy" (p. 4).
Research Gap CỤ THỂ: Nghiên cứu này giải quyết một khoảng trống rõ ràng trong lĩnh vực tối ưu hóa chương trình song song, đó là sự phụ thuộc vào "việc lập hồ sơ mở rộng và điều chỉnh thủ công" (p. 4). Phương pháp hiện hành này không chỉ "tốn thời gian về thời gian của lập trình viên và máy tính" mà còn "không hiệu quả đối với tất cả các chương trình, chẳng hạn như chương trình bất định hình và chương trình tuần tự được thực thi trong các hệ thống song song động" (p. 4). Ngay cả các hệ thống song song tự động hiện có như Cilk [38] và Dynamic Resolution [45] cũng yêu cầu "điều chỉnh thủ công nhiều để đặt ngưỡng trên cơ sở từng chương trình" và các ngưỡng này "không thể di động giữa các máy có đặc điểm khác nhau" (p. 6). Luận án này lấp đầy khoảng trống đó bằng cách cung cấp một giải pháp tự động, di động, thích ứng và có thể dự đoán được.
Research Questions và Hypotheses: Luận án tập trung giải quyết câu hỏi trung tâm:
- Đối với một chương trình song song cụ thể chạy trên một hệ thống song song cụ thể, số lượng luồng song song nào sẽ mang lại thời gian thực thi tối thiểu?
Các câu hỏi phụ khám phá sự phức tạp của vấn đề: 2. Điều gì sẽ xảy ra nếu các đặc điểm của hệ thống đích không xác định trước thời gian thực thi? 3. Điều gì sẽ xảy ra nếu các yêu cầu của chương trình không xác định trước thời gian thực thi?
Giả thuyết trung tâm của luận án là một phương pháp mới, được gọi là "predictive adaptive parallelism", có thể tự động tính toán số lượng luồng tối ưu tại thời điểm chạy bằng cách kết hợp thông tin biên dịch và thời gian chạy, từ đó giảm thiểu thời gian thực thi chương trình một cách hiệu quả và đáng tin cậy.
Theoretical Framework: Khung lý thuyết của nghiên cứu này xoay quanh khái niệm "Predictive Adaptive Parallelism". Nó tích hợp các nguyên tắc từ nhiều lĩnh vực:
- Lý thuyết hiệu suất máy tính (Computer Performance Theory): Thông qua việc sử dụng "Performance Vectors" [57][58] để định lượng khả năng của phần cứng.
- Lý thuyết tải chia (Divisible Load Theory) [10]: Các mô hình phương trình chi phí được phát triển trong luận án (ví dụ: Equation 4.22) mở rộng lý thuyết tải chia bằng cách kết hợp chi phí truyền thông và chi phí khởi tạo luồng vào một hàm chi phí tổng thể có thể tối ưu hóa.
- Lý thuyết tối ưu hóa toán học: Sử dụng phép tính vi phân để tìm điểm cực tiểu của các hàm chi phí thực thi, xác định số lượng luồng tối ưu.
Đóng góp đột phá với quantified impact: Luận án này đưa ra một số đóng góp mang tính đột phá:
- Phương pháp mới lạ để tính toán số lượng luồng tối ưu tự động: Luận án giới thiệu "predictive adaptive parallelism, ... một phương pháp mới để tự động tính toán số lượng luồng tối ưu cho các chương trình song song tại thời điểm chạy" (p. 4). Điều này có tác động định lượng đáng kể, có khả năng "tiết kiệm thời gian của lập trình viên, thời gian biên dịch lại và thời gian lập hồ sơ" (p. 6), chuyển đổi tài nguyên từ các hoạt động điều chỉnh thủ công sang các tác vụ sản xuất.
- Mô tả chương trình độc lập với nền tảng: Phát triển "load vectors độc lập với nền tảng" mô tả chi phí thực thi một phần chương trình và "cost functions" mô tả số lần mỗi phần sẽ được thực thi (p. 4). Khả năng này mang lại lợi ích to lớn về tính di động, cho phép các chương trình thích ứng với các hệ thống mục tiêu khác nhau mà không cần sửa đổi mã nguồn.
- Tối ưu hóa thích ứng và có thể dự đoán được: Hệ thống được thiết kế để "có thể tự động điều chỉnh theo những thay đổi trong đặc điểm hệ thống mà không cần sự can thiệp thủ công" (tính di động), "có thể tối ưu hóa chương trình để đáp ứng với những thay đổi về kích thước tập dữ liệu hoặc sự bất định hình có thể dự đoán được khác" (tính thích ứng), và "có thể dự đoán số lượng luồng tối ưu cần sử dụng cho một phân đoạn chương trình song song mà không cần chạy phân đoạn chương trình đó trước hoặc lưu trữ thông tin lịch sử về các lần chạy trước" (tính dự đoán) (p. 6). Những thuộc tính này mở rộng khả năng áp dụng tính toán song song cho nhiều loại ứng dụng hơn, đặc biệt là các chương trình bất định hình.
- Mô hình toán học cho việc giảm thiểu thời gian thực thi: Xây dựng các mô hình toán học chi tiết (ví dụ: phương trình 4.22) để mô tả thời gian thực thi của một chương trình như một hàm của số lượng luồng. Bằng cách tính đạo hàm và giải cho số lượng luồng, luận án cung cấp một công thức chính xác để tìm số lượng luồng tối ưu (ví dụ: phương trình 4.23 trên p. 37). Đối với thuật toán Jacobi Relaxation với A = 10000 và n = 3, số luồng tối ưu được tính toán là "~35" (p. 24), thể hiện khả năng dự đoán định lượng.
- Tích hợp kỹ thuật đặc trưng hóa máy nâng cao: Luận án tích hợp "Performance Vectors" [57][58] để đặc trưng hóa hiệu suất phần cứng một cách nhanh chóng và chính xác. Nghiên cứu này cũng chỉ ra rằng "linear least squares có thể được sử dụng để tính toán performance vector và, ngay cả khi nó chứa các giá trị âm nhỏ, vẫn có thể mang lại dự đoán thời gian hiệu suất chính xác hơn" trong "64.2% thời gian" (p. 28).
Scope và Significance:
Phạm vi của nghiên cứu này tập trung vào các "hệ thống song song đồng nhất nơi thời gian giao tiếp giữa hai bộ xử lý bất kỳ là đồng nhất (hoặc đủ gần để có hiệu quả đồng nhất)" (p. 5), bao gồm các hệ thống cụm (cluster systems) và hệ thống đa xử lý đối xứng bộ nhớ chia sẻ (shared-memory symmetric multiprocessor systems). Các phương pháp được áp dụng cho "loop-level parallelism và task-level parallelism" (p. 5).
Về mặt định lượng, các ví dụ thực nghiệm cho thuật toán Jacobi Relaxation sử dụng các kích thước ma trận (A) từ 32 đến 1024 (p. 67-72), minh họa khả năng thích ứng của phương pháp với các kích thước tập dữ liệu khác nhau.
Tính quan trọng của luận án là rất lớn, vì nó cung cấp một giải pháp cơ bản cho việc tự động hóa tối ưu hóa chương trình song song, một yếu tố then chốt để khai thác toàn bộ tiềm năng của kiến trúc đa lõi và song song đang phát triển.
Literature Review và Positioning
Nghiên cứu về tính toán song song đã phát triển qua nhiều dòng chính. Một dòng quan trọng là kỹ thuật biên dịch song song (parallelizing compiler techniques), nơi các trình biên dịch cố gắng tự động tìm và khai thác sự song song trong mã tuần tự. Một dòng khác là hệ thống tối ưu hóa thời gian chạy động hoàn toàn (full dynamic runtime optimizing systems), vốn thực hiện các quyết định tối ưu hóa trong quá trình thực thi chương trình. Các hệ thống như Cilk [38] và Dynamic Resolution [45] thuộc dòng này, cố gắng tự động song song hóa các chương trình tuần tự bằng cách xác định các đoạn mã có thể thực thi song song tại thời điểm chạy.
Tuy nhiên, có những mâu thuẫn và tranh luận trong các phương pháp này. Mặc dù lý thuyết cho rằng "sử dụng n bộ xử lý sẽ tăng tốc độ thực thi chương trình lên n lần" (p. 3), nhưng thực tế là "tốc độ tăng tuyến tính gần như không bao giờ đạt được; gần như tất cả các chương trình song song đều cho thấy lợi nhuận giảm dần khi sử dụng thêm bộ xử lý" (p. 3). Điều này là do "việc sử dụng tài nguyên bổ sung không miễn phí," mà phát sinh "chi phí chung lớn hơn nhiều so với các chương trình tuần tự" (p. 3).
Một vấn đề khác là mặc dù các hệ thống song song hóa tự động như Cilk [38] và Dynamic Resolution [45] đã giới thiệu "tự động hóa hữu ích vào thời gian chạy chương trình," chúng "vẫn yêu cầu nhiều điều chỉnh thủ công để đặt ngưỡng trên cơ sở từng chương trình, và các ngưỡng này không di động giữa các máy có đặc điểm khác nhau" (p. 6). Điều này tạo ra một rào cản đáng kể cho tính di động và khả năng thích ứng.
Positioning trong Literature: Luận án này định vị mình bằng cách lấp đầy khoảng trống tồn tại giữa các kỹ thuật biên dịch song song tĩnh và các hệ thống tối ưu hóa thời gian chạy động, nhưng thiếu khả năng dự đoán và thích ứng thực sự. Cụ thể, nó tập trung vào việc giải quyết vấn đề "điều chỉnh thủ công và lập hồ sơ" (p. 4) vốn đang là phương pháp thịnh hành để tìm số lượng luồng tối ưu.
How this advances field: "Predictive Adaptive Parallelism" tiến xa hơn bằng cách cung cấp một khuôn khổ tự động, có thể dự đoán và thích ứng. Nó vượt qua giới hạn của việc điều chỉnh thủ công bằng cách tạo ra "các hàm chi phí có thể được giải để đưa ra một hồ sơ thời gian thực thi chương trình như một hàm của số lượng luồng được gán cho chương trình" (p. 4). Điều này cho phép hệ thống "tự động điều chỉnh theo những thay đổi trong đặc điểm hệ thống mà không cần sự can thiệp thủ công" (p. 6) và "tối ưu hóa chương trình để đáp ứng với những thay đổi về kích thước tập dữ liệu hoặc sự bất định hình có thể dự đoán được khác" (p. 6).
So sánh với ÍT NHẤT 2 international studies:
- Cilk [38] (MIT/Intel): Cilk là một hệ thống song song hóa tự động có ảnh hưởng, được phát triển tại MIT, tập trung vào việc dễ dàng song song hóa các chương trình đệ quy. Tuy nhiên, như luận án đã chỉ ra, Cilk và các công cụ tương tự "vẫn yêu cầu nhiều điều chỉnh thủ công để đặt ngưỡng" để quyết định khi nào nên tạo khối lượng công việc song song (p. 6). Phương pháp của Wangerin vượt trội hơn Cilk ở khía cạnh này bằng cách cung cấp một cách tiếp cận toán học để xác định tính lợi nhuận của việc song song hóa, loại bỏ nhu cầu về các ngưỡng được điều chỉnh thủ công và cải thiện tính di động giữa các môi trường máy khác nhau.
- Dynamic Resolution [45] (Nghiên cứu tương tự về song song hóa động): Tương tự như Cilk, Dynamic Resolution là một hệ thống tự động song song hóa các chương trình tuần tự tại thời điểm chạy. Nó cũng phải đối mặt với thách thức "xác định quá nhiều sự song song hóa và việc thực thi chương trình bị quá tải với chi phí chung của việc tạo ra khối lượng công việc song song mới" (p. 6). Wangerin's Predictive Adaptive Parallelism cung cấp một giải pháp cho vấn đề này thông qua các hàm chi phí dự đoán có thể "xác định lợi nhuận của việc sử dụng sự song song hóa," do đó tránh được chi phí chung không cần thiết (p. 7). Điều này đại diện cho một bước tiến quan trọng so với các phương pháp này, đặc biệt là khi các đoạn mã song song "thường là duy nhất, có nghĩa là mã song song chưa được xác định trước đó, và có thể chỉ thực thi một lần duy nhất" (p. 7), làm cho việc lập hồ sơ là không thể.
Đóng góp lý thuyết và khung phân tích
Đóng góp cho lý thuyết
Luận án này đóng góp đáng kể vào lý thuyết tính toán song song bằng cách mở rộng các khuôn khổ hiện có và cung cấp một mô hình mới để quản lý tài nguyên động.
- Mở rộng/thách thức các lý thuyết cụ thể: Nghiên cứu này không trực tiếp thách thức các lý thuyết nền tảng, mà thay vào đó, nó mở rộng các lý thuyết hiện có về hiệu suất tính toán và phân bổ tài nguyên. Nó bổ sung một lớp động, có thể dự đoán được vào các mô hình hiệu suất tĩnh hoặc dựa trên kinh nghiệm. Cụ thể, nó mở rộng khuôn khổ của Performance Vectors [57][58] bằng cách tích hợp chúng vào một hệ thống runtime để đưa ra các quyết định phân bổ tài nguyên động. Hơn nữa, nó mở rộng Lý thuyết tải chia (Divisible Load Theory) [10] bằng cách cung cấp một mô hình toán học chi tiết kết hợp các chi phí chung thực tế của giao tiếp và khởi tạo luồng vào một hàm chi phí tổng thể có thể tối ưu hóa.
- Conceptual Framework (Khung khái niệm): Khung khái niệm chính là "Predictive Adaptive Parallelism," bao gồm bốn thành phần cốt lõi:
- Load Vectors: Mô tả tài nguyên cần thiết của các đoạn chương trình một cách độc lập với nền tảng.
- Cost Functions: Mô tả luồng điều khiển của các đoạn chương trình song song và số lần mỗi đoạn sẽ được thực thi, với số lượng luồng là một biến.
- Machine Characterization (Performance Vectors): Mô tả khả năng hiệu suất của máy mục tiêu.
- Runtime System: Hệ thống gắn kết các thành phần này lại với nhau để tính toán số lượng luồng tối ưu. Mối quan hệ giữa các thành phần này được minh họa rõ ràng trong "Hình 3.1: Chuyển đổi chi phí chương trình từ các load vector độc lập với máy thành ước tính thời gian phụ thuộc vào máy" (p. 13), cho thấy một luồng thông tin logic từ mô tả độc lập đến ước tính thời gian cụ thể và có thể tối ưu hóa.
- Theoretical Model (Mô hình lý thuyết): Các mô hình lý thuyết được trình bày dưới dạng các phương trình toán học mô tả thời gian thực thi của một đoạn chương trình song song dưới dạng một hàm của số lượng luồng (t). Ví dụ, đối với một vòng lặp có một chỉ số cơ sở, phương trình chi phí tổng quát là:
Q(t) = (A/t) * (B + C) + Dt(p. 16, Equation 3.1, sau khi sửa C từ chi phí truyền thông thành chi phí giao tiếp và G*epsilon cho bandwidth). Một mô hình toàn diện hơn, tích hợp truyền thông và băng thông, được trình bày dưới dạng:Q(t) = (A/t) * (B + n*(G*epsilon)) + 2Dt(p. 37, Equation 4.22) trong đó:tlà số lượng luồng.Alà tổng đơn vị công việc (ví dụ: tổng số lần lặp cho vòng lặp).Blà chi phí tính toán cho mỗi đơn vị công việc.nlà số lần giao tiếp trên mỗi lần lặp.Glà kích thước dữ liệu được truyền.epsilonlà băng thông (đơn vị thời gian trên mỗi đơn vị dữ liệu).Dlà chi phí chung trên mỗi luồng (ví dụ: chi phí khởi tạo luồng). Các đạo hàm của các phương trình này được sử dụng để tìm số lượng luồng tối ưu (t) bằng cách đặtdQ(t)/dt = 0, ví dụ:t = sqrt((A * (B + n*(G*epsilon))) / (2D))(p. 37, Equation 4.23).
- Paradigm Shift (Chuyển đổi mô hình): Luận án này đại diện cho một sự chuyển đổi mô hình từ việc tối ưu hóa song song chủ yếu dựa trên kinh nghiệm và điều chỉnh thủ công sang một phương pháp tiếp cận định lượng, dựa trên mô hình và tự động. Bằng chứng cho điều này là mục tiêu rõ ràng của luận án là thay thế "việc lập hồ sơ mở rộng và điều chỉnh thủ công" (p. 4) bằng một hệ thống "tự động tính toán số lượng luồng tối ưu" (p. 4).
Khung phân tích độc đáo
- Integration của theories: Nghiên cứu này tích hợp thành công các lý thuyết về kiến trúc máy tính (Computer Architecture) thông qua Performance Vectors, lý thuyết tối ưu hóa (Optimization Theory) thông qua việc giảm thiểu hàm chi phí, và các nguyên tắc của lập trình song song (Parallel Programming) thông qua các mô hình về chi phí tính toán và giao tiếp.
- Novel analytical approach: Cách tiếp cận phân tích mới lạ nằm ở khả năng tạo ra và giải các hàm chi phí thực thi động tại thời điểm chạy. Điều này cho phép "ước tính thời gian có thể được tính toán lại nếu các tham số thay đổi" (p. 13), mang lại sự linh hoạt và khả năng thích ứng chưa từng có. Lý do cho cách tiếp cận này được chứng minh bởi nhu cầu giải quyết tính di động, khả năng thích ứng và khả năng dự đoán (p. 6), vốn không được giải quyết đầy đủ bởi các phương pháp trước đây.
- Conceptual contributions: Luận án định nghĩa rõ ràng các khái niệm như "Load Vectors" (mô tả độc lập với nền tảng về nội dung lệnh của các đoạn chương trình, p. 29) và "Cost Functions" (mô tả thời gian biên dịch về luồng điều khiển của các đoạn chương trình song song, p. 15), cung cấp một ngôn ngữ hình thức để phân tích hiệu suất song song.
- Boundary conditions explicitly stated: Các điều kiện biên giới của khung phân tích được nêu rõ. Hệ thống được nhắm mục tiêu cho "hệ thống song song đồng nhất" (p. 5) và giải quyết "tính bất định hình từ kích thước tập dữ liệu" (p. 7) chứ không phải "tính bất định hình từ các giá trị dữ liệu" (p. 7) vốn không thể dự đoán được. Luận án cũng phân biệt rõ ràng giữa việc lập lịch "nhiều chương trình song song độc lập" và "lập lịch các luồng thuộc cùng một chương trình," tập trung vào loại thứ hai (p. 5).
Phương pháp nghiên cứu tiên tiến
Nghiên cứu áp dụng một phương pháp kết hợp mô hình hóa lý thuyết, phát triển hệ thống và xác nhận thực nghiệm để giải quyết vấn đề phân bổ tài nguyên động trong tính toán song song.
Thiết kế nghiên cứu
- Research philosophy: Phương pháp luận này rõ ràng tuân theo triết lý nghiên cứu Positivism và lập trường nhận thức luận Objectivism. Nó tìm cách phát triển các mô hình định lượng (ví dụ: các phương trình chi phí, công thức số luồng tối ưu) để giải thích và dự đoán một cách khách quan hành vi của các chương trình song song. Việc nhấn mạnh vào "đo lường chính xác các ước tính thời gian thực thi luồng" (p. 26) và "được đưa ra thời gian thực thi của các lệnh trong điều kiện thực tế" (p. 27) phản ánh niềm tin rằng kiến thức có thể được thu thập thông qua việc quan sát và đo lường khách quan.
- Mixed methods: Mặc dù không phải là "mixed methods" theo nghĩa xã hội học, thiết kế này kết hợp các thành phần lý thuyết (phát triển mô hình toán học) và thực nghiệm (xác nhận hệ thống trên phần cứng thực tế). Các phương pháp luận bao gồm phân tích biên dịch thời gian để tạo load vectors, kỹ thuật đặc trưng hóa máy để tạo performance vectors, và giải các hàm toán học tại thời điểm chạy.
- Multi-level design: Phân tích hoạt động ở nhiều cấp độ: từ các "basic blocks" (p. 29) là các tập hợp lệnh nguyên tử, đến "loop-level parallelism" và "task-level parallelism" (p. 5) là các phân đoạn chương trình lớn hơn. Điều này cho phép xây dựng các mô hình chi phí chi tiết và có thể tổng hợp được.
- Sample size và selection criteria EXACT: Để đặc trưng hóa máy, "performance vectors" được tạo ra bằng cách chạy "một bộ benchmarks đại diện cho các ứng dụng thực tế" (p. 27). Mặc dù kích thước cụ thể của bộ benchmark không được nêu chi tiết, nó được nhấn mạnh rằng "cần phải đảm bảo rằng bộ benchmark bao gồm các chương trình tương tự như các chương trình mà chúng sẽ được sử dụng để ước tính thời gian thực thi" (p. 28). Đối với các thử nghiệm, thuật toán Jacobi Relaxation được sử dụng với các kích thước ma trận
Atừ32đến1024và số lần lặp (num_iter) là1hoặc2(p. 67-72). Ví dụ minh họa sử dụngA = 10000vàn = 3(số lần lặp) trên một máy lý thuyết (p. 24).
Quy trình nghiên cứu rigorous
- Sampling strategy: Chiến lược không phải là lấy mẫu thống kê, mà là lựa chọn các chương trình benchmark. "Performance vectors được phát triển cho một máy chỉ một lần. Các giá trị là tĩnh và sẽ không thay đổi trừ khi bộ benchmark được thay đổi" (p. 28).
- Data collection protocols: Để tạo performance vectors, "các bộ đếm và các kỹ thuật không xâm lấn khác thu thập thông tin thời gian và số lượng lệnh" (p. 27). Điều này đảm bảo rằng dữ liệu thu thập được phản ánh "thời gian thực thi thực tế của các lệnh trong điều kiện thực tế" (p. 27).
- Triangulation: Việc kết hợp mô hình toán học dự đoán với thử nghiệm thực nghiệm trên "hệ thống cluster" (p. 5) đóng vai trò là một hình thức kiểm định chéo. Các mô hình lý thuyết được xác nhận thông qua các kết quả thực nghiệm, minh họa tính "hiệu quả và chính xác" (p. 5) của phương pháp.
- Validity (construct/internal/external) và reliability (α values): Tính hợp lệ được đảm bảo bằng cách đảm bảo rằng "performance vectors... phản ánh hiệu suất thực tế, không phải hiệu suất đỉnh" (p. 26). Tính tin cậy được hỗ trợ bởi thực tế là các performance vectors được tính toán một lần duy nhất từ bộ benchmark và có thể được tái sử dụng. Mặc dù các giá trị
alpha(ví dụ: Cronbach's alpha) không được áp dụng trực tiếp trong bối cảnh này, sự nhấn mạnh vào "dự đoán thời gian hiệu suất chính xác hơn" (p. 28) và việc kiểm tra độ nhạy của phương pháp đối với sự không chính xác trong việc đo lường khả năng của máy (p. 5) thể hiện mối quan tâm đến tính tin cậy của các phép đo.
Data và phân tích
- Sample characteristics: Đối với thuật toán Jacobi Relaxation, dữ liệu bao gồm các cấu hình kích thước ma trận khác nhau (ví dụ:
A=32, A=64, ..., A=1024) và số lần lặp (1 hoặc 2) (p. 67-72, Bảng 5.9 và 5.10). Các đặc điểm này cho phép đánh giá hiệu suất của phương pháp trên nhiều khối lượng công việc có thể dự đoán được. - Advanced techniques: Các kỹ thuật phân tích tiên tiến bao gồm việc sử dụng phép tính vi phân để tối ưu hóa hàm chi phí, tìm số lượng luồng tối ưu (p. 16). Để tính toán performance vectors, luận án so sánh các phương pháp khác nhau, bao gồm cả việc sử dụng "linear least squares" (p. 28), ngay cả khi nó có thể tạo ra các giá trị âm nhỏ. Mặc dù không có tên phần mềm cụ thể nào được đưa ra trong các đoạn văn bản được cung cấp, việc đề cập đến "Performance Vectors [57][58]" ngụ ý việc sử dụng các công cụ lập hồ sơ hệ thống và các công cụ toán học để giải quyết các hệ thống quá mức.
- Robustness checks: Luận án "khám phá độ nhạy của phương pháp đối với sự không chính xác trong việc đo lường khả năng của máy" (p. 5), điều này rất quan trọng để đánh giá tính mạnh mẽ của mô hình trong các điều kiện không lý tưởng. Điều này được thảo luận cụ thể hơn trong Chương 4.5, "Sensitivity of Performance Vectors" (p. 58-59).
- Effect sizes và confidence intervals: Mặc dù không được báo cáo theo cách truyền thống bằng
p-valueshoặcconfidence intervals, luận án cung cấp bằng chứng định lượng về hiệu suất tối ưu, ví dụ, "số lượng luồng tối ưu là ~35" (p. 24) cho một trường hợp cụ thể, và khẳng định rằng "least squares đã đưa ra câu trả lời chính xác hơn 64.2% thời gian" (p. 28) cho việc dự đoán performance vector, cung cấp các chỉ số thực nghiệm về hiệu quả của phương pháp.
Phát hiện đột phá và implications
Những phát hiện then chốt
Nghiên cứu của Wangerin đã tạo ra một số phát hiện then chốt, mang tính đột phá cho lĩnh vực tính toán song song:
- Khả năng tự động tính toán số luồng tối ưu tại runtime: Phát hiện quan trọng nhất là phương pháp "predictive adaptive parallelism" có thể tự động xác định số lượng luồng tối ưu cho các chương trình song song tại runtime, bao gồm cả các chương trình bất định hình. Điều này được hỗ trợ bởi sự thành công của phương pháp khi được áp dụng cho "loop-level parallelism và task-level parallelism" và "kỹ thuật này được chứng minh là hiệu quả và chính xác trên hệ thống cluster" (p. 5).
- Mối quan hệ parabol giữa thời gian thực thi và số luồng: Phát hiện này khẳng định rằng thời gian thực thi của một chương trình song song ban đầu giảm khi tăng số luồng nhưng sau đó "sẽ đi ngang và cuối cùng thậm chí còn tăng lên" (p. 10). Mối quan hệ này được minh họa rõ nét trong "Hình 3.8: Hồ sơ thời gian của thuật toán Jacobi Relaxation song song" (p. 25), cho thấy một đường cong parabol với điểm tối thiểu rõ ràng, xác nhận rằng có một "số lượng luồng tối ưu là ~35" cho các tham số đã cho (p. 24). Điều này là một kết quả định lượng cụ thể từ dữ liệu mô phỏng.
- Hiệu quả của Load Vectors và Cost Functions: Luận án chứng minh rằng việc kết hợp các load vectors độc lập với nền tảng và các cost functions có thể dự đoán được là một cách hiệu quả để mô tả yêu cầu tài nguyên của chương trình và khả năng của máy mục tiêu. "Nếu các tham số thay đổi, các ước tính thời gian có thể được tính toán lại" (p. 13), cho thấy tính thích ứng cao.
- Tính ưu việt của Linear Least Squares trong tính toán Performance Vector: Mặc dù không phải là đóng góp chính, phát hiện rằng "linear least squares có thể được sử dụng để tính toán performance vector và, ngay cả khi nó chứa các giá trị âm nhỏ, vẫn có thể mang lại dự đoán thời gian hiệu suất chính xác hơn" trong "64.2% thời gian" (p. 28) cung cấp một cải tiến cụ thể trong kỹ thuật đặc trưng hóa máy.
- Ứng dụng thành công cho Jacobi Relaxation: Việc áp dụng phương pháp cho thuật toán Jacobi Relaxation, một ví dụ tiêu biểu về tính toán khoa học, đã chứng minh tính khả thi và độ chính xác của Predictive Adaptive Parallelism trong việc tìm kiếm cấu hình luồng tối ưu cho các kích thước tập dữ liệu khác nhau (A = 32 đến A = 1024, p. 67-72).
- Statistical significance (p-values, effect sizes): Mặc dù không được báo cáo dưới dạng p-value hay effect sizes cụ thể trong các đoạn trích dẫn, các kết quả định lượng như "optimal number of threads is ~35" (p. 24) và "accuracy 64.2% of the time" (p. 28) đóng vai trò là bằng chứng thực nghiệm cho tính hiệu quả của phương pháp.
- Counter-intuitive results: "Using extra resources adds extra overhead, and the more resources that are used, the more overhead that is incurred" (p. 3). Điều này dẫn đến kết quả "adding processors to a parallel program will not always decrease the processing time" (p. 10), là một kết quả nền tảng nhưng thường gây ngạc nhiên cho người mới bắt đầu.
- Compare with prior research findings: Các phát hiện này khác biệt rõ rệt với các phương pháp trước đây chủ yếu dựa vào thử nghiệm và sai sót hoặc "điều chỉnh thủ công nhiều" (p. 6), cung cấp một giải pháp tự động và có thể dự đoán.
Implications đa chiều
- Theoretical advances: Nghiên cứu này cung cấp một khuôn khổ toán học mạnh mẽ cho việc quản lý tài nguyên động trong các hệ thống song song, mở rộng các lý thuyết hiện có về mô hình hóa hiệu suất và phân bổ tải (chẳng hạn như Divisible Load Theory [10]). Nó cũng cung cấp một cơ sở lý thuyết cho việc thiết kế các hệ thống runtime thích ứng.
- Methodological innovations: Phương pháp luận tiên tiến của việc kết hợp thông tin compile-time và run-time để tạo ra các hàm chi phí tối ưu hóa có thể áp dụng cho các bối cảnh khác ngoài Jacobi Relaxation, bao gồm nhiều loại "loop-level parallelism" và "task-level parallelism" (p. 5), mở ra hướng nghiên cứu về các trình biên dịch thông minh hơn và hệ thống runtime thích ứng.
- Practical applications: Các ứng dụng thực tế là rất lớn. Phương pháp này có thể "tiết kiệm thời gian của lập trình viên, thời gian biên dịch lại và thời gian lập hồ sơ" (p. 6), cho phép các nhà phát triển tập trung vào việc tạo mã mới thay vì duy trì hoặc điều chỉnh mã cũ. Điều này đặc biệt có lợi cho các ứng dụng như "xử lý hình ảnh và các quy trình đại số tuyến tính" (p. 6) có khối lượng công việc phụ thuộc vào tập dữ liệu đầu vào. Nó cũng "dễ dàng phát triển các chương trình song song" (p. 6).
- Policy recommendations: Mặc dù không trực tiếp là chính sách, nhưng những phát hiện này có thể định hướng cho việc phát triển các tiêu chuẩn phần mềm và phần cứng cho tính toán hiệu suất cao, khuyến khích tích hợp các khả năng thích ứng và dự đoán vào các hệ điều hành và công cụ lập trình.
- Generalizability conditions: Phương pháp này được thiết kế để "áp dụng cho nhiều loại ứng dụng, chẳng hạn như các chương trình song song thông thường, một số dạng chương trình song song bất định hình và các chương trình chạy trên hệ thống song song động" (p. 5). Tuy nhiên, các điều kiện tổng quát hóa được quy định rõ ràng: hệ thống phải là "đồng nhất" và tập trung vào "tính bất định hình từ kích thước tập dữ liệu" chứ không phải từ giá trị dữ liệu (p. 5, 7).
Limitations và Future Research
Mọi nghiên cứu học thuật đều có những giới hạn riêng, và luận án này cũng không ngoại lệ, đồng thời mở ra những hướng nghiên cứu phong phú trong tương lai.
3-4 specific limitations acknowledged
- Hệ thống đồng nhất và mạng lưới chuyên biệt: Luận án tập trung vào "hệ thống song song đồng nhất nơi thời gian giao tiếp giữa hai bộ xử lý bất kỳ là đồng nhất" (p. 5). Mặc dù phương pháp này áp dụng tốt cho hệ thống cụm và hệ thống đa xử lý đối xứng, nó thừa nhận rằng đối với các "mạng lưới chuyên biệt được tìm thấy trên một số siêu máy tính chuyên dụng, chẳng hạn như vòng, cây mỡ, siêu khối và hình xuyến ba chiều," thì "các phương pháp được trình bày trong công trình này sẽ cần sửa đổi mở rộng để sử dụng các mô hình" (p. 5). Điều này cho thấy giới hạn trong việc áp dụng cho các kiến trúc HPC đa dạng và phức tạp hơn.
- Tính bất định hình từ giá trị dữ liệu: Nghiên cứu này chủ yếu giải quyết "tính bất định hình từ kích thước tập dữ liệu," nơi các yêu cầu tài nguyên có thể được biết tại điểm vào của vòng lặp hoặc điều kiện (p. 7). Tuy nhiên, nó thẳng thắn thừa nhận rằng "tính bất định hình từ giá trị dữ liệu không có tính chất dự đoán; trên thực tế, thường không thể đưa ra bất kỳ dự đoán nào về giá trị dữ liệu" (p. 7). Điều này bỏ ngỏ một phần lớn các chương trình có hành vi phụ thuộc vào dữ liệu.
- Phạm vi lập lịch: Luận án chỉ xem xét "lập lịch các luồng thuộc cùng một chương trình" (p. 5). Nó nêu rõ rằng "lập lịch các chương trình độc lập là một vấn đề lớn hơn nhiều và nằm ngoài phạm vi của công trình này" (p. 5). Điều này hạn chế khả năng áp dụng của phương pháp trong các môi trường đa nhiệm phức tạp, nơi nhiều chương trình song song có thể tranh giành tài nguyên.
- Giả định về giao tiếp: Mô hình giao tiếp giả định rằng "tất cả các độ trễ sẽ là đồng nhất, và nhiều giao tiếp điểm-điểm có thể xảy ra đồng thời" (p. 33). Đây là một sự đơn giản hóa có thể không hoàn toàn đúng trong các hệ thống thực tế, đặc biệt là với độ nhiễu và sự thay đổi trong mạng.
Boundary conditions về context/sample/time
- Context: Các phương pháp được thiết kế và xác nhận trong bối cảnh các hệ thống đồng nhất, thường là các hệ thống cluster, và SMP systems, nơi chi phí giao tiếp và tính toán có thể được mô hình hóa một cách đồng nhất.
- Sample: Các ví dụ tập trung vào các chương trình song song cấp độ vòng lặp và cấp độ tác vụ, đặc biệt là những chương trình có tính bất định hình có thể dự đoán được dựa trên kích thước tập dữ liệu.
- Time: Nghiên cứu phản ánh trạng thái công nghệ và các thách thức trong tính toán song song tính đến năm 2006.
Future research agenda với 4-5 concrete directions
Luận án này tự coi mình là "một mảnh ghép của câu đố để tự động hóa song song" (p. 2), mở ra một chương trình nghiên cứu rộng lớn:
- Mở rộng sang hệ thống dị chủng và mạng lưới chuyên biệt: Một hướng rõ ràng là sửa đổi các phương pháp để hoạt động hiệu quả trên "hệ thống dị chủng và các mạng lưới chuyên biệt" (p. 5), nơi các đặc điểm hiệu suất của bộ xử lý và mạng lưới không đồng nhất.
- Giải quyết tính bất định hình không thể dự đoán: Phát triển các kỹ thuật để xử lý "tính bất định hình từ giá trị dữ liệu," có thể liên quan đến các phương pháp dựa trên học máy hoặc phân tích thống kê nâng cao để dự đoán hành vi không xác định.
- Tích hợp lập lịch chương trình độc lập: Mở rộng hệ thống để tích hợp với "lập lịch các chương trình độc lập," xử lý sự cạnh tranh tài nguyên giữa nhiều ứng dụng song song chạy đồng thời.
- Tự động hóa hoàn toàn việc tạo Load Vectors và Cost Functions: Mục tiêu dài hạn là "tự động hóa việc tạo ra các load vector và cost function cho các mã song song tùy ý" (p. 24), giảm thiểu sự can thiệp thủ công từ lập trình viên.
- Cải thiện mô hình giao tiếp và chi phí chung: Nghiên cứu sâu hơn về mô hình hóa chi phí giao tiếp phức tạp hơn, bao gồm tắc nghẽn mạng, độ nhiễu và các cơ chế giao tiếp không đồng bộ, cũng như các thành phần chi phí chung tinh vi hơn.
Methodological improvements suggested
- Tinh chỉnh các kỹ thuật tính toán performance vector, ví dụ, tiếp tục nghiên cứu các phương pháp giải hệ phương trình quá định (overdetermined systems) tốt hơn linear least squares, đặc biệt là để tránh các giá trị âm và cải thiện độ chính xác dự đoán.
Theoretical extensions proposed
- Xây dựng các mô hình lý thuyết toàn diện hơn cho các cấu trúc song song lồng nhau (nested parallel segments), các đoạn song song liền kề (adjacent parallel segments) và song song đường ống (pipeline parallelism), như đã được gợi ý trong mục lục Chương 4. Điều này sẽ đòi hỏi việc mở rộng các hàm chi phí để nắm bắt sự phức tạp tăng lên của các tương tác.
Tác động và ảnh hưởng
Luận án "Predictive Adaptive Parallelism" của David L. Wangerin có tiềm năng tạo ra tác động và ảnh hưởng sâu rộng trong nhiều lĩnh vực.
- Academic impact (Tác động học thuật): Nghiên cứu này thiết lập một khuôn khổ lý thuyết và phương pháp luận mạnh mẽ cho việc quản lý tài nguyên động trong các hệ thống song song, có khả năng trở thành nền tảng cho các công trình nghiên cứu trong tương lai. Các khái niệm về load vectors, cost functions và việc sử dụng performance vectors cho tối ưu hóa runtime sẽ cung cấp một ngôn ngữ và công cụ mới cho các nhà nghiên cứu. Ước tính số lượng trích dẫn tiềm năng là đáng kể, vì nó giải quyết một vấn đề cốt lõi và kéo dài trong tính toán song song. Các phương trình chi phí và công thức tối ưu hóa có thể trở thành tài liệu tham khảo tiêu chuẩn.
- Industry transformation (Chuyển đổi công nghiệp): Luận án có thể tạo ra một "chuyển đổi" trong cách các chương trình song song được phát triển và triển khai trong ngành công nghiệp. Bằng cách tự động hóa quá trình điều chỉnh, nó "tiết kiệm thời gian của lập trình viên, thời gian biên dịch lại và thời gian lập hồ sơ" (p. 6), làm giảm đáng kể chi phí và độ phức tạp của việc phát triển ứng dụng song song. Điều này sẽ đặc biệt có lợi cho các ngành yêu cầu tính toán hiệu suất cao như:
- Khoa học dữ liệu và AI: Tăng tốc độ đào tạo mô hình và xử lý dữ liệu lớn.
- Kỹ thuật và mô phỏng: Các ứng dụng như "mô hình dự báo thời tiết" (p. 3) hoặc "ứng dụng gấp protein" (p. 3) có thể được hưởng lợi từ việc tối ưu hóa tài nguyên hiệu quả hơn, giảm thời gian tính toán từ "ngày" xuống "giờ" hoặc từ "cả đời" xuống "thời gian khả thi".
- Phát triển phần mềm: Các lập trình viên có thể sử dụng máy thử nghiệm với các đặc điểm khác với máy đích và "vẫn đạt được hiệu suất đầy đủ" (p. 6), nâng cao tính di động của mã.
- Policy influence (Ảnh hưởng chính sách): Mặc dù không trực tiếp là chính sách chính phủ, nghiên cứu này có thể ảnh hưởng đến các chính sách và tiêu chuẩn phát triển công cụ phần mềm (compilers, runtime libraries) cho các hệ thống song song. Nó thúc đẩy ý tưởng về các hệ thống có khả năng tự động thích ứng, có thể dẫn đến việc ưu tiên tài trợ cho nghiên cứu về quản lý tài nguyên tự động và các trình biên dịch thông minh hơn ở cấp độ quốc gia và quốc tế.
- Societal benefits (Lợi ích xã hội): Lợi ích cuối cùng được định lượng, dù gián tiếp, là khả năng giải quyết các thách thức tính toán lớn hơn và phức tạp hơn một cách nhanh chóng. Việc tăng tốc độ tính toán cho các vấn đề như "dự báo thời tiết" (p. 3) có thể mang lại lợi ích trực tiếp cho an toàn công cộng và hoạch định chính sách. Tương tự, việc thúc đẩy các lĩnh vực như "ứng dụng gấp protein hoặc phân tích mã hóa" (p. 3) có thể dẫn đến những đột phá trong y học hoặc an ninh mạng, với tác động tích cực đến toàn xã hội.
- International relevance (Tính liên quan quốc tế): Vấn đề tối ưu hóa chương trình song song là một thách thức toàn cầu. Các giải pháp cho tính di động, thích ứng và dự đoán là vô cùng quan trọng đối với các trung tâm siêu máy tính, các phòng thí nghiệm nghiên cứu và các tập đoàn công nghệ trên toàn thế giới. Bằng cách cung cấp một phương pháp giải quyết vấn đề cơ bản này, luận án có ý nghĩa quốc tế sâu sắc và có thể được áp dụng rộng rãi trên các hệ thống và môi trường khác nhau.
Đối tượng hưởng lợi
Nghiên cứu của Wangerin mang lại lợi ích cụ thể cho nhiều đối tượng khác nhau trong cộng đồng học thuật và công nghiệp.
- Doctoral researchers (Các nhà nghiên cứu tiến sĩ):
- Gaps nghiên cứu cụ thể: Luận án cung cấp một nền tảng vững chắc và làm nổi bật các "gaps" nghiên cứu rõ ràng cho các luận án tiến sĩ trong tương lai. Ví dụ, việc mở rộng phương pháp này sang các hệ thống dị chủng (heterogeneous systems), xử lý tính bất định hình không thể dự đoán được từ giá trị dữ liệu (irregularity from data values, p. 7), hoặc tích hợp với việc lập lịch các chương trình song song độc lập (p. 5) đều là những hướng nghiên cứu có giá trị.
- Phương pháp luận: Cung cấp một ví dụ điển hình về việc kết hợp mô hình hóa lý thuyết với xác minh thực nghiệm trong lĩnh vực khoa học máy tính.
- Senior academics (Các học giả cao cấp):
- Theoretical advances: Đóng góp một khuôn khổ lý thuyết mới cho quản lý tài nguyên động trong tính toán song song, làm giàu thêm các cuộc thảo luận học thuật về tối ưu hóa hệ thống. Các học giả có thể xây dựng trên mô hình Predictive Adaptive Parallelism để phát triển các lý thuyết phức tạp hơn về hiệu suất hệ thống và phân bổ tài nguyên.
- Hướng dẫn cho hệ thống runtime: Cung cấp các nguyên tắc thiết kế cho các hệ thống runtime tự động và thích ứng, có thể thúc đẩy nghiên cứu về các trình biên dịch thông minh và kiến trúc hệ điều hành.
- Industry R&D (Nghiên cứu và Phát triển công nghiệp):
- Practical applications: Giải pháp của Wangerin có thể được áp dụng trực tiếp trong việc phát triển các công cụ biên dịch và thư viện runtime để tự động tối ưu hóa các ứng dụng song song. Lợi ích định lượng bao gồm "tiết kiệm thời gian của lập trình viên, thời gian biên dịch lại và thời gian lập hồ sơ" (p. 6), ước tính hàng ngàn giờ công và tài nguyên tính toán cho các dự án lớn.
- Cải thiện hiệu suất sản phẩm: Các công ty phát triển phần mềm có thể tạo ra các sản phẩm hiệu quả hơn, có khả năng tự điều chỉnh để phù hợp với các cấu hình phần cứng khác nhau mà không cần điều chỉnh thủ công, giảm chi phí hỗ trợ và tăng sự hài lòng của khách hàng.
- Policy makers (Các nhà hoạch định chính sách):
- Mặc dù ít trực tiếp hơn, nhưng nghiên cứu này có thể cung cấp bằng chứng cho việc đầu tư vào các công nghệ tính toán hiệu suất cao tự động. Nó nhấn mạnh nhu cầu về các giải pháp giúp khai thác tối đa tài nguyên tính toán, có ý nghĩa đối với các chính sách liên quan đến nghiên cứu khoa học, cơ sở hạ tầng siêu máy tính và phát triển công nghệ quốc gia.
- Quantify benefits (Định lượng lợi ích):
- Đối với các lập trình viên, phương pháp này loại bỏ nhu cầu "chạy và lập hồ sơ chương trình để tìm hiểu mức độ mở rộng của nó" (p. 4), chuyển đổi thời gian điều chỉnh thủ công thành thời gian phát triển sản phẩm thực tế.
- Đối với người dùng cuối, nó hứa hẹn tốc độ thực thi nhanh hơn và hiệu quả hơn cho các ứng dụng quan trọng, ví dụ, giúp các "mô hình dự báo thời tiết" (p. 3) đưa ra kết quả kịp thời, hoặc giảm thiểu thời gian xử lý cho các tác vụ "protein folding" (p. 3) từ "cả đời" xuống một khoảng thời gian hợp lý.
- Trong ví dụ về thuật toán Jacobi Relaxation, hệ thống có thể tự động tìm ra số luồng tối ưu là "~35" (p. 24) thay vì yêu cầu người dùng phải thử nghiệm nhiều lần, giảm thời gian tìm kiếm tối ưu xuống gần như bằng không.
Câu hỏi chuyên sâu
-
Theoretical contribution độc đáo nhất (name theory extended): Đóng góp lý thuyết độc đáo nhất của luận án là việc tạo ra một khuôn khổ Predictive Adaptive Parallelism để tự động xác định số lượng luồng tối ưu tại thời điểm chạy. Điều này mở rộng đáng kể các lý thuyết hiện có về mô hình hóa hiệu suất và phân bổ tài nguyên, đặc biệt là Performance Vectors [57][58] và Divisible Load Theory [10]. Thay vì chỉ đặc trưng hóa hiệu suất tĩnh hoặc phân bổ tải dựa trên các giả định đơn giản, Wangerin tích hợp khả năng dự đoán động dựa trên thông tin compile-time (load vectors) và run-time (cost functions, base metrics, performance vectors) vào một mô hình tối ưu hóa bằng phép tính vi phân. Điều này vượt xa các phương pháp truyền thống bằng cách cung cấp một cơ chế tự động, di động và thích ứng để giải quyết vấn đề phân bổ tài nguyên, giải quyết một khoảng trống mà các hệ thống song song tự động như Cilk [38] và Dynamic Resolution [45] chưa giải quyết được hoàn toàn do vẫn yêu cầu điều chỉnh thủ công các ngưỡng.
-
Methodology innovation (compare với 2+ prior studies): Đổi mới phương pháp luận then chốt là việc phát triển một hệ thống bán động kết hợp thông tin compile-time và run-time để tính toán số lượng luồng tối ưu một cách tự động. Điều này khác biệt rõ rệt so với các phương pháp trước đây:
- So với phương pháp "lập hồ sơ mở rộng và điều chỉnh thủ công" (p. 4): Đây là "phương pháp phổ biến hiện nay" nhưng "tốn thời gian" và "không hiệu quả đối với tất cả các chương trình" (p. 4). Phương pháp của Wangerin loại bỏ nhu cầu điều chỉnh thủ công bằng cách tự động hóa quá trình xác định số luồng tối ưu thông qua các mô hình toán học và đánh giá runtime.
- So với các hệ thống song song tự động như Cilk [38] và Dynamic Resolution [45]: Các hệ thống này "thường xác định quá nhiều sự song song hóa" và "yêu cầu nhiều điều chỉnh thủ công để đặt ngưỡng" (p. 6), cũng như thiếu tính di động. Phương pháp của Wangerin cung cấp một cơ chế dự đoán "lợi nhuận của việc sử dụng sự song song hóa" (p. 7) mà không cần các ngưỡng cố định, giúp tránh chi phí chung không cần thiết và tăng tính di động. Sự tích hợp các load vectors độc lập với nền tảng, performance vectors đặc trưng hóa máy, và các hàm chi phí toán học cho phép đưa ra các quyết định thông minh hơn và tự động hơn tại runtime.
-
Most surprising finding (với data support): Phát hiện đáng ngạc nhiên nhất, mặc dù là nền tảng cho luận án, là việc tăng thêm bộ xử lý không phải lúc nào cũng làm giảm thời gian xử lý. Trên thực tế, "đối với một chương trình song song điển hình, khi các bộ xử lý được thêm vào, thời gian xử lý ban đầu sẽ giảm nhưng sau đó sẽ đi ngang và cuối cùng thậm chí còn tăng lên" (p. 10). Điều này trực quan được thể hiện trong "Hình 3.8: Hồ sơ thời gian của thuật toán Jacobi Relaxation song song" (p. 25). Biểu đồ này hiển thị rõ ràng một đường cong hình parabol, cho thấy thời gian thực thi tối thiểu tại khoảng
35 luồngvới các tham sốA = 10000, B = 62, C = 2003, D = 1500, n = 3. Nếu số luồng tiếp tục tăng vượt quá điểm này, thời gian thực thi bắt đầu tăng lên, chứng minh rằng quá nhiều tài nguyên có thể gây bất lợi do chi phí chung liên quan đến việc quản lý chúng. -
Replication protocol provided? Có, luận án cung cấp một giao thức nhân rộng đầy đủ và chi tiết. Quy trình được nêu rõ qua các bước:
- Biên dịch chương trình: Trình biên dịch sẽ chèn "load vectors" (mô tả độc lập với nền tảng về nội dung lệnh của các đoạn chương trình) và "cost functions" (mô tả luồng điều khiển và số lần thực thi của các đoạn chương trình) vào mã (p. 12, 14-15).
- Đặc trưng hóa máy: Máy mục tiêu được "lập hồ sơ để xây dựng đặc điểm về khả năng hiệu suất của nó, được gọi là performance vector cho hệ thống" (p. 12), bằng cách chạy một bộ benchmark và thu thập dữ liệu về thời gian và số lượng lệnh (p. 26-28).
- Thực thi runtime: Tại runtime, load vectors và performance vector được kết hợp để gán chi phí thời gian cho mỗi đoạn chương trình. Khi các tham số chương trình (ví dụ: kích thước tập dữ liệu) trở nên rõ ràng, các cost functions được đánh giá để tạo ra các phương trình mô tả thời gian thực thi dưới dạng hàm của số lượng luồng (p. 12, 15-16).
- Tối ưu hóa: Bằng cách tính đạo hàm của hàm chi phí và giải cho số lượng luồng, số luồng tối ưu có thể được xác định (ví dụ:
t = sqrt((AB + AC) / D)từ Equation 3.2, p. 16, hoặc Equation 4.23, p. 37). Ví dụ chi tiết về thuật toán Jacobi Relaxation (p. 17-24) minh họa cụ thể cách áp dụng các bước này, cho phép các nhà nghiên cứu khác tái tạo và xác nhận phương pháp.
-
10-year research agenda outlined? Mặc dù không trực tiếp là "chương trình nghiên cứu 10 năm" với mốc thời gian cụ thể, luận án đã phác thảo một chương trình nghiên cứu mở rộng có thể dễ dàng kéo dài trong nhiều năm. Tuyên bố "Luận án này đại diện cho một mảnh ghép của câu đố để tự động hóa song song" (p. 2) ngụ ý một tầm nhìn dài hạn. Các hướng nghiên cứu cụ thể được đề xuất bao gồm:
- Mở rộng phương pháp cho các hệ thống dị chủng và mạng lưới chuyên biệt (p. 5).
- Xử lý tính bất định hình từ giá trị dữ liệu (irregularity from data values), vốn hiện tại không thể dự đoán được (p. 7).
- Tích hợp giải pháp với việc lập lịch các chương trình độc lập (p. 5).
- Tự động hóa hoàn toàn việc tạo các load vector và cost function cho các mã song song tùy ý (p. 24).
- Nghiên cứu các mô hình phức tạp hơn cho lồng nhau, liền kề và song song đường ống (được gợi ý trong mục lục Chương 4). Những hướng này đại diện cho các lĩnh vực phức tạp đòi hỏi nỗ lực nghiên cứu đáng kể, phù hợp với một chương trình dài hạn.
Kết luận
Luận án "Predictive Adaptive Parallelism" của David L. Wangerin đại diện cho một bước tiến quan trọng trong lĩnh vực tính toán song song, giải quyết vấn đề quản lý tài nguyên động một cách toàn diện và đột phá.
Nghiên cứu đã đưa ra 5 đóng góp cụ thể và nổi bật:
- Giới thiệu phương pháp "Predictive Adaptive Parallelism," một cơ chế tự động để tính toán số lượng luồng tối ưu tại thời điểm chạy, loại bỏ nhu cầu điều chỉnh thủ công.
- Phát triển các "load vectors" độc lập với nền tảng và "cost functions" có thể dự đoán được, cho phép mô tả chương trình di động và thích ứng.
- Chứng minh hiệu quả và độ chính xác của phương pháp trên hệ thống cụm, bao gồm các ứng dụng song song cấp độ vòng lặp và cấp độ tác vụ.
- Xây dựng một khung toán học vững chắc, sử dụng các hàm chi phí và phép tính vi phân để tối thiểu hóa thời gian thực thi chương trình.
- Xác định rằng Linear Least Squares là một kỹ thuật hiệu quả để tạo Performance Vectors, cải thiện độ chính xác dự đoán.
Những đóng góp này thúc đẩy một chuyển đổi mô hình từ việc tối ưu hóa song song dựa trên kinh nghiệm và điều chỉnh thủ công sang một phương pháp tiếp cận định lượng, dựa trên mô hình và tự động. Bằng chứng rõ ràng về khả năng thay thế "việc lập hồ sơ mở rộng và điều chỉnh thủ công" (p. 4) bằng một hệ thống dự đoán và thích ứng đánh dấu sự tiến bộ này.
Nghiên cứu này cũng đã mở ra 3+ luồng nghiên cứu mới quan trọng:
- Mở rộng khả năng của Predictive Adaptive Parallelism cho hệ thống dị chủng và các mạng lưới chuyên biệt vốn phức tạp hơn các hệ thống đồng nhất hiện đang được tập trung.
- Phát triển các kỹ thuật để xử lý tính bất định hình không thể dự đoán được từ giá trị dữ liệu, một thách thức lớn đối với việc dự đoán hành vi chương trình.
- Tích hợp các nguyên tắc của luận án vào các hệ thống lập lịch chương trình độc lập quy mô lớn, vượt ra ngoài việc quản lý các luồng trong một chương trình duy nhất.
- Hoàn thiện việc tự động hóa hoàn toàn việc tạo ra các load vector và cost function cho bất kỳ mã song song nào.
Với tính liên quan toàn cầu, vấn đề tối ưu hóa hiệu suất song song là phổ quát. Các tổ chức nghiên cứu và công nghiệp trên toàn thế giới đối mặt với cùng một thách thức trong việc khai thác tối đa sức mạnh của các hệ thống đa lõi và cụm. Giải pháp của Wangerin mang lại một mô hình có thể áp dụng quốc tế, cung cấp một phương pháp thống nhất để tối ưu hóa tài nguyên.
Di sản của luận án này là tạo ra các kết quả đo lường được, bao gồm việc giảm đáng kể "thời gian của lập trình viên, thời gian biên dịch lại và thời gian lập hồ sơ" (p. 6), đồng thời tăng cường hiệu quả thực thi các ứng dụng quan trọng trong khoa học, kỹ thuật và phân tích dữ liệu. Bằng cách cho phép các chương trình tự điều chỉnh để tìm số lượng luồng tối ưu (như ví dụ với ~35 luồng cho Jacobi Relaxation trên p. 24), nó góp phần vào việc sử dụng tài nguyên máy tính một cách thông minh hơn, cuối cùng dẫn đến các tính toán nhanh hơn và các đột phá khoa học sớm hơn.
Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộUNIVERSITY OF CALIFORNIA, IRVINE Predictive Adaptive Parallelism DISSERTATION submitted in partial satisfaction of the requirements for the degree of DOCTOR OF PHILOSOPHY in Information and Computer Science by David L. Wangerin Dissertation Committee: Professor Isaac D. Scherson, Chair Professor Alex Nicolau Professor Alex Veidenbaum 2006 UMI Number: 3243277 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction.
In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3243277 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved.
This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © 2006 David L. Wangerin The dissertation of David L.
Wangerin is approved and is acceptable in quality and form for publication on microfilm: Ts lao =e = mmfftee Chair University of California, Irvine 2006 ii TABLE OF CONTENTS LIST OF FIGURES Vv LIST OF TABLES VII ACKNOWLEDGMENTS VIII CURRICULUM VITAE IX ABSTRACT OF THE DISSERTATION xX 1 FOREWORD 1 2 INTRODUCTION 3 2. Q Q Q Q Q Quy và va 10 3 SOLUTION OUTLINE 12 3. vn v VN cv VN va 14 3.4 Example of the System. cv v g k v v k k v k Và 29 43 Loop Level Parallelism.4 Multiple Program Segments .41 Nested Parallel Segments.2 Adjacent Parallel Segments .3 Concurrent Parallel Segments.5 Sensitivity of Performance Vectors.6 Task Level Parallelism.
eee eee ee 56 5 ANALYSIS OF SOLUTION 60 5.3 Jacobi Relaxation Algorithm. 0000000004 90 iil 6 PREVIOUS WORK 91 6.2 Parallelizing Compiler Techniques .3 Full Dynamic Runtime Optimizing Systems. 101 7 CONCLUSIONS AND FUTURE WORK 104 7. ee 105 BIBLIOGRAPHY 114 APPENDICES A Instruction Classes.v và xà B Parallel Python.
ee C Benchmark Set. ee v2 iv LIST OF FIGURES 2.1 Irregularity from data set size.2 Irregularity from data values.3 Choice of how to divide a parallel program.1 Program cost and time translations.2 Jacobi relaxation algorithm in HPE.3 Visual representation of two iterations of the Jacobi relaxation algorithm.4 Division of the data set for the parallel Jacobi relaxation algorithm.5 Structure of a generic thread in the parallel Jacobi relaxation algorithm.6 Pseudocode for a parallel Jacobi relaxation algorithm.7 The load vectors for each section of the parallel Jacobi relaxation al- gorithm. ng cv kg k NV kia 22 3.8 Time profile of the parallel Jacobi relaxation algorithm.1 Visualization of a performance vector with two instruction classes.2 Example of the load vector created from a single basic block.3 Basic block structure of a while loop and repeat loop.4 The load vector from a loop with a regular loop variant.5 The load vector from an irregular loop with an identifiable and pre- dictable loop variant.6 The load vector from a base metric loop.7 Basic block structure of a conditional if-then-else statement.8 Structure of an embarrassingly parallel program.9 Typical timing curve of equation (4.10 Two adjacent parallel sections with communications in the transition between sections. HQ HH ng và Tà xa 42 4.11 Time plot of two adjacent program segments.12 Two parallel sections that execute concurrently.13 Time profile of two program segments under case (1).14 Time profile of two program segments under case (2).15 Time profile of two program segments under case (3).16 Time profile to execute two program segments simultaneously while minimizing the total processing time.17 Time profile of executing three program segments simultaneously.18 Structure of a program using pipeline parallelism.1 Time plot on a fast system.
ee ee ee 61 5.2 Time plot on a medium system.3 Time plot on a slow system.4 Time plot of the same program on three different systems.9 The kernel of the 1-dimensional Jacobi relaxation algorithm.6 The client code for parallel Jacobi relaxation.7 Timing of network packet transmissions.8 Closeup of the low range of packet sizes and timing.9 Timing results for A= 32.10 Timing results for A=64.11 Timing results for A= 128.12 Timing results for A= 256.13 Timing results for A=512, 2.14 Timing results for Á = 1024.15 Timing results for A = 32, 2 iterations.16 Timing results for A = 64, 2 iterations.17 Timing results for A= 128, 2 iterations.18 Timing results for A = 256, 2iterations.19 Timing results for A = 512, 2iterations.20 Timing results for A = 1024, 2 iterations.1 Data decomposition of a matrix for a heterogeneous system. 106 vi LIST OF ‘TABLES 3.1 Machine and program cost characteristics.1 Comparison between scheduling methods for two program segments.1 Performance vectors for the three machines.2 Sensitivity of the performance vector memory value.3 Sensitivity with large memory values.4 Configuration of the test cluster.5 Instruction counts and timing results from the benchmark set.6 Performance vectors using memory-only and least squares models.7 Load vectors for the parallel Jacobi relaxation algorithm.8 Optimal number of threads for Jacobi relaxation algorithm.9 Optimal number of threads for Jacobi relaxation algorithm with 2 it- erations. vii ACKNOWLEDGEMENTS First and foremost, I would like to thank Issac Scherson for being a wonderful adviser, a great friend, and a constant source of inspiration. I first met Isaac in my under- graduate career, and it was by his suggestion that I became involved in research.
If it were not for Isaac, I would never have pursued a graduate degree. I am, and always will be, in debt to him for all of his great advice and help. I am also very grateful for the help and advice of my committee members Alex Nicolau and Alex Veidenbaum. Their feedback and critiques have been both invalu- able and through-provoking, and they have greatly increased the quality of my work.
I would like to thank everyone in my family (and soon to be family) for their constant love and support. I can’t express how much it has meant to me. I would also like to thank everyone from my research group, whose comments, insights, and help have been invaluable. In particular I would like to thank Shean McMahon and John Duselis for their hours of help with working on frustrating math- ematical problems, proof-reading papers, discussing difficult problems, and providing encouragement when I got stuck.
My education and research endeavors have been enriched by my experiences work- ing with NASA Goddard, NASA JPL, Unisys, the UC-MEXUS program, and of course UCI. In particular, I would like to thank John Dorband, Raphael Some, Mike Haken, and the great faculty of UCI. Last but not least, I would like to thank Rob Kolstad who has always given me great advice and pushed me to pursue hard and interesting problems. Vili CURRICULUM VITAE David L.
in Information and Computer Science, University of California, Irvine. 2005-2006 Software Developer, TMT Laboratories, Huntington Beach, California. 2005 Summer Researcher Fellowship, University of California, Irvine. in Information and Computer Science, University of California, Irvine.
2003-2004 Teaching Assistant, Information and Computer Science, University of California, Irvine. 2001 Internship, NASA Goddard Space Flight Center, VSEP Program, Greenbelt, Maryland. in Information and Computer Science, University of California, Irvine. 1998-2002 Co-op, Unisys Corporation, Systems Analysis, Modeling and Measurement Group, Mission Viejo, California.
Publications e David Wangerin and Isaac D. Using Predictive Adaptive Parallelism to Address Portability and Irregularity. In Proceedings of the 2005 Interna- tional Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2005), Las Vegas, Nevada, USA, December 2005. e David Wangerin and Isaac D.
Automatic Resource Management using an Adaptive Parallelism Environment. In Proceedings of the 2003 IEEE Inter- national Parallel and Distributed Processing Symposium (IPDPS) Workshop on Massively Parallel Processing, Nice, France, April 2003. A Modular Client-Server Discrete Event Simulator for Networked Computers. In Proceedings of the 35th Annual Simulation Symposium 2002, San Diego, California, USA, April 2002.
ix ABSTRACT OF THE DISSERTATION Predictive Adaptive Parallelism By David L. Wangerin Doctor of Philosophy in Information and Computer Science University of California, Irvine, 2006 Professor Isaac D. Scherson, Chair Parallel processing is used to increase the execution rate of programs. Since pro- cessing resources are the bottleneck for processing speed, increasing the processing rate is accomplished by adding more processing resources to the system.
However, using extra resources adds extra overhead, and the more resources that are used, the more overhead that is incurred. Optimal performance for parallel programs is achieved by finding the correct balance between computational speedup and overhead of using parallel resources. The current method of optimizing parallel programs is through extensive profiling and manual tuning of programs. This is not ideal since it is both time consuming in terms of programmer and machine time, and does not work for all programs, such as irregular programs and sequential programs executed in dynamic parallel systems.
A novel method, called predictive adaptive parallelism, is presented for automat- ically calculating the optimal number of threads for parallel programs at runtime. The method uses a combination of compile-time and run-time information to gauge the program resource requirements and target machine capabilities. Programs are x described in platform-independent load vectors, which describe the cost of executing a section of a program, and cost functions, which describe the number of times each section will be executed. When the programs are loaded onto a machine, the load vectors are translated into time costs.
As runtime metrics become known, the cost functions can be solved to give a time profile of executing the program as a function of the number of threads assigned to the program. Minimizing the cost function yields the minimal execution time of the program and thus the optimal number of threads. The method is applied to loop-level parallelism and task-level parallelism, and the techniques are shown to be effective and accurate on a cluster system. In addition, the sensitivity of the method to inaccuracy in measuring the machine capabilities is explored.
xi CHAPTER Í FOREWORD A personal anecdote: when I first entered college, I bought a dual-processor computer system. I was extremely excited about it, not the least because I had purchased the system piecemeal over the span of a year with all the money I earned from my job. I had the expectation that with a second processor, all the programs on my system would run about twice as fast. However, after I completed the system and got it running, it seemed that everything ran at about the same speed as when I only had a single processor.
In fact, after running some tests with game frame rates and other simple benchmarking tools available to me, it turned out that all the programs really were running at the same speed as with a single processor. This was both very frustrating and confusing!. The experience was not all bad, as it led me to wonder why the second processor did not add to the execution speed of typical programs. After some investigation, I found out that writing programs to use more than one processor is difficult— difficult enough that for the most part it is only done when programs require it.
This is both because the programming tools for parallel processing are somewhat primitive and because of the fact that using extra processors does not always give a speedup as expected, i., there is more to the problem than just throwing resources at it. Parallel programs need to use different data structures and figure out how to partition the data among the processors, need to use communications between processors to share data, and need to coordinate the activities of all processors to avoid problems like race conditions, deadlocks, and using old data. In addition, debugging parallel programs 1To make the experience even worse, the motherboard had a faulty capacitor that literally burned up and destroyed the motherboard a few months after I added the second processor. Needless to say, the replacement was a single processor system.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Trích dẫn luận án này
David L. Wangerin (2006). Predictive Adaptive Parallelism - Luận án tiến sĩ [Luận án tiến sĩ, University of California, Irvine]. LuanAn.net. https://luanan.net/cong-nghe-thong-tin/khoa-hoc-may-tinh/luan-an-tien-si-predictive-adaptive-parallelism
Từ khóa và chủ đề nghiên cứu
Từ khóa liên quan
Chủ đề nghiên cứu
Câu hỏi thường gặp
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" nghiên cứu về vấn đề gì?
Luận án tiến sĩ về song song thích ứng dự đoán. Đề xuất phương pháp tối ưu hiệu suất máy tính đa xử lý qua dự đoán động và phân chia công việc thích ứng.
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại University of California, Irvine. Năm bảo vệ: 2006.
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" thuộc chuyên ngành gì?
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" thuộc chuyên ngành Information and Computer Science. Danh mục: Khoa Học Máy Tính.
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" có bao nhiêu trang?
Luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" có 145 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "Predictive Adaptive Parallelism - Luận án tiến sĩ" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.