نمونه سوال موازی

مرجع:

http://people.scs.carleton.ca/~maheshwa/courses/4009COMP/outline.html

http://people.scs.carleton.ca/~maheshwa/courses/409/409.html

P1[10 Marks] Suppose a linear array consisting of n processors (labeled P_0 to P_{n-1}) contains

n natural numbers. You need to design an algorithm so that processor

P_0 outputs YES if all the input numbers are distinct, otherwise

it answers  NO. Justify why your algorithm is correct, its complexity and is it optimal?

هر پردازنده عدد خود را به پردازنده‌ی با اندیس یکی کمتر از خودش بفرستد و اگر تساوی رخ داد YES را به بعدی بفرستد. بدیهی است که در هر زمان بیش از یک عدد از یک لینک عبور نمی‌کند چون هر پردازنده فقط یک عدد دارد. بعد از n گام عدد پردازنده‌ی آخر به پردازنده‌ی اول رسیده است پس در این زمان اگر در پردازنده‌ی اول YES داشتیم یعنی جواب yes است و در غیر این صورت no است.

Question 2 (15 Marks) 

Design an algorithm for sorting N numbers on an O(log N)-processor linear array that is 100% efficient. (Assume that N/log N numbers are with each processor. Recall that efficiency is ratio of the running time of the best sequential algorithm to the work of parallel algorithm. Work of a parallel algorithm is the product of its running time and number of processors.)

جواب:

Efficiency = 1 ==> speed up = p = O(log n)

sort = O(n log n)

==> T_parallel = O(n)

اگر بخواهیم الگوریتم معمولی را با تعداد پردازنده‌ی کمتری اجرا کنیم (طبق راهنمایی سوال) داریم:

T_sort_1_processor (serial) = O( n / log n log (n/logn) ) = O(n)

سپس روی آن الگوریتم مرتب سازی زوج و فرد را اجرا می‌کنیم با فرض اینکه بیش از یک عدد در هر پردازنده هست. یعنی در هر عمل ابتدا لیست دو پردازنده را ادغام می‌کنیم و نیمه‌ی کمتر را به پردازنده سمت چپ و نیمه‌ی بیشتر را به پردازنده‌ی سمت راست می‌دهیم. مشابه مرتب سازی زوج و فرد این کار به تعداد پردازنده‌ها گام نیاز دارد که O(log n) است پس کل الگوریتم O(n) می‌شود و بهینه است.

Question 3 ( 15 Marks) Show that sorting the rows and then the columns of a mesh leaves the rows in sorted order. 

از قضیه صفر و یک استفاده می‌کنیم: اگر الگوریتمی مجموعه‌ای از ۰ و ۱ ها را درست مرتب کند، همه‌ی اعداد را درست مرتب می‌کند.

اگر در یک ستون مقدار سطر پایینی جایگزین سطر بالایی شود یعنی عنصر سطر بالایی ۱ و عنصر سطر پایینی صفر بوده است پس همه‌ی عناصر سطر بالایی که سطر پایینی برای آنها ۱ است جایگزین می‌شوند. در جهت عکس سمت چپ جا به جا می‌شود. در حالتی که اعداد دو سطر مساوی باشند بدیهی است که جابه‌جایی صورت نمی‌گیرد و اگر صورت بگیرد هم تأثیری ندارد.

P1[15 Marks] (Leftmost 1 problem) Let A be a Boolean array of size n.

a) Develp an T(n)=O(1) time (common) CRCW PRAM algorithm to find the smallest index k such that A(k) = 1. The total number of operations must be W(n)=O(n).

هر پردازنده‌ای که عدد یک دارد اندیس خود را در خانه‌ی حافظه‌ی جواب می‌نویسد ولی عدد کوچکتر در جواب نوشته می‌شود. چون نوشتن همزمان داریم می‌توانیم آن را با یک سربار لگاریتمی به مینیمم گرفتن تبدیل کنیم.

b) How fast can you solve this problem on CREW PRAM using O(n) operations.

به جواب قسمت قبل مراجعه شود.

P2[15 Marks] Suppose you are given n integers in the range [0...log n]. Develop an O(log n) time EREW PRAM sorting algorithm that uses O(n) operations.

با روش مرتب سازی سطلی عمل می‌کنیم. هر یک از این لگاریتم عدد متمایز را یک سطل می‌گیریم و تعداد عناصر هر سطل را به دست می‌آوریم. زمان لگاریتمی برای تبدیل افزایش همزمان که در ERCW است به EREW است. سپس جمع پیشوندی را حساب می‌کنیم و بازه‌ی هر کدام از اعداد در جواب به دست می‌آید سپس هر پردازنده بازه‌ی خود را نگاه می‌کند از بین این لگاریتم زوج عدد پیدا می‌کند و آن عدد را می‌نویسد. این راه حل در مدل CREW است که باعث می‌شود یک لگاریتم برای تبدیل آن به مدل EREW لازم شود.

P3[20 Marks] Show how you can compute the maximum of of n elements in O(1) parallel time using n^{1+c} processors, c is a constant and is a real number  > 0 (e.g c could be 0.25). Use Common-CRCW PRAM for this problem and look into accelarated cascading. Write down your algorithm in terms of Steps and analyze its complexity. 

هر کسی عدد خودش را در جواب می‌نویسد و ماکسیمم آنها باقی می‌ماند.

DETERMINISTIC SAMPLE SORT:

input: p processors (numbered 0 to p-1), each processor has an array of n/p items.

output: all p arrays are sorted GLOBALLY (p0 < p1 < p2 < ...)

ALGORITHM:

step 1: locally, each processor sorts its array sequentially (you may use C's quicksort).

step 2: locally, each processor picks p equally spaced elements; i.e. every (n/p^2)th element. These elemnts are called the "splitters".

step 3: all processors send their p splitters to proc. #0.

step 4: proc. #0 sorts all p^2 splitters and picks each p-th splitter, obtaining p-1 "global splitters".

step 5: proc. #0 broadcasts the p-1 global splitters to all processors.

step 6: For proc. #i let B(i,j) be the j-th bucket of its local data with respect to the global splitters; i.e. the local data between the (j-1)-th and j-th global splitter. Each processor #i computes its p buckets B(i,j), 0 <= j <= p-1, and sends (in 1 h-relation total) every B(i,j) to proc. #j.

step 7: Let b(j) be the union of B(0,j), B(1,j), B(2,j), ..., B(p-1,j); i.e. b(j) is the data received by proc. #j in step 6. Each proc. #j, locally (sequentially) sorts b(j).

Question 1 (20 MARKS):

Show that b(j) <= 2 n/p for all 0 <= j <= p-1.

Question 3 (15 Marks)  Refer to Lemma 3.3 on page 401 of Leighton's book. Show that if G_i can be embedded in G'_i with dilation d for 1<=i<=k, then G can be embedded in G' with dilation d.

Question 4 (15 Marks) Show that an N-node hypercube contains Theta(log N) edge-disjoint copies  of a sqrt(N)*sqrt(N) mesh.

اصلاحیه حل تمرین موازی

سوال آخر تمرین ۳ که خواسته است رابطه بازگشتی تو در تو حل کنیم با parallel prefix با فرض بینهایت پردازنده در زمان O(log n) حل می‌شود که زمان parallel prefix و semigroup است چون زمان مراحل موازی با هم ماکسیمم گرفته می‌شوند یک مرحله محاسبه‌ی پیشوند داریم و دو مرحله جمع جملات (semigroup) داریم.

Geometric Optimization (Fall 2013)

مرجع: http://www.cs.tau.ac.il/~michas/optcourse.html

استاد: Sharir

The syllabus of the course 

===== 

The syllabus may not exactly coincide with the material that will be taught. It will be (slightly) updated during the semester 

===== 

(1) Parametric Searching:

The basic technique

Illustration: Slope selection

Issues in parallel computation

Cole's improvement

Alternatives: Probabilistic approach, Expanders, Monotone Matrix Searching, Chan's technique

===== 

(2) Linear Programming: Geometric Approach:

Review of Megiddo's algorithm and Seidel's randomized algorithm. Algorithms by Clarkson and by Matousek et al.

Abstract linear programming: Framework, geometric applications, variants

===== 

(3) Search in Monotone Matrices: 

===== 

(4) Facility Location:

The p-center probolem

Efficient algorithm for the 2-center problem

Exact and approximate algorithms for the general case

Clustering

The p-median problem and other variants

===== 

(5) Diameter in Three Dimensions:

A randomized algorithm

A deterministic algorithm

===== 

(6) Geometric Optimization and Arrangements:

Hausdorff distances

Width in three dimensions

Polygon placements; biggest stick in a polygon.

===== 

(7) Shortest Paths:

Shortest paths in the plane

Shortest paths on a convex polytope and in polyhedral 3-D regions

Approximate shortest paths

===== 

(8) Approximation Algorithms for Geometric Optimization:

Euclidean travelling salesperson

Approximating diameter, width, minimum-width annuli and cylinders

===== 

(9) Approximate Nearest Neighbor Search in Higher Dimensions:

Review of recent techniques

online auctions

http://www.cs.umd.edu/~hajiagha/AGT10/13-10-10-OnlineAuctions.pdf

مشخصات توپولوژی‌های مختلف (موازی)

جواب سوال آخر تمرین ۳ پردازش موازی

اصلا سعی نکنید این سوال را حل کنید الکی وقتتون تلف میشه!

http://en.wikipedia.org/wiki/Newton_polynomial

http://en.wikipedia.org/wiki/Divided_differences

Mind maths: Small world with big connections

دریافت

مرجع

Robust Shape Fitting via Peeling and Grating Coresets

http://www.cs.duke.edu/~pankaj/publications/papers/core-outlier.pdf

Let P be a set of n points in R^d. A subset S of P is called a (k,epsilon)-kernel if for every direction, the

direction width of S epsilon-approximates that of P, when k outliers can be ignored in that direction.

Width of Points in the Streaming Model

http://www.mit.edu/~andoni/papers/width.pdf

موضوع آن محاسبه‌ی عرض نقاط به صورت dynamic یعنی با اضافه شدن نقطه و حذف شدن نقطه است. در آن از ورونوی دیاگرام گسسته هم استفاده شده است و مبنای الگوریتم عرض جهتی است.

سوالات میان ترم تقریبی