Home » Forums » Ruby » Ruby in General

โจทย์ Matrix Multiplication

  • warning: realpath() [function.realpath]: SAFE MODE Restriction in effect. The script whose uid is 1005 is not allowed to access /tmp owned by uid 0 in /var/www/sites/sugree/codenone.com/subdomains/www/html/includes/file.inc on line 190.
  • warning: realpath() [function.realpath]: SAFE MODE Restriction in effect. The script whose uid is 1005 is not allowed to access /tmp owned by uid 0 in /var/www/sites/sugree/codenone.com/subdomains/www/html/includes/file.inc on line 190.
Submitted by pphetra on 26 January, 2007 - 21:29

จาก http://www.codenone.com/node/121
ลองเขียนคูณ matrix อีกแบบ
เรื่องเวลาไม่เร็วขึ้น มีแต่ช้าลง

หลักการที่ทดลองก็คือ MapReduce อันเลื่องชื่อของ google
process หน้าตาเป็นแบบนี้

 +---------+     +----------+     +----------+
 |  split  | --> | map func.| --> | reduce   |
 +---------+     +----------+     +----------+

เริ่มด้วยการแบ่งงานออกเป็นชิ้นย่อยๆ
งานแต่ละงานจะประกอบด้วย key กับ value
ในที่นี้เนื่องจากขี้เกียจเลยแบ่งงานออกง่ายๆแบบนี้


          |1 2 3|
          |4 5 6|
          |7 8 9|

  |1 2 3|  a b c
  |4 5 6|  d e f
  |7 8 9|  g h i

a,b,c,..,i คืองานย่อยที่จะส่งไปให้ map function ทำงาน
อย่าง task a ก็จะมีหน้าตาแบบนี้ [0,0,[1,2,3],[1,4,7]]
0,0 คือ ค่า key ที่แสดงถึง coordinate, ซึ่ง reduce process
จะใช้เป็นข้อมูลในการประกอบข้อมูลกลับเป็น matrix ผลลัทธ์

  +------+                           +---------+                                 +-------+
  |split |->  [a, b, c, d, ..., i] ->|map func.| -> [a', b', c', d', ..., i'] -> |reduce |
  +------+                           +---------+                                 +-------+       


  a = [0,0,[1,2,3],[1,4,7]
  a'= [0,0,30]
  b = [0,1,[1,2,3],[2,5,8]
  b'= [0,1,36]
  ...

ในส่วน distributed เราใช้ module rinda ซึ่งมีอยู่ใน package มาตรฐานของ ruby
ไม่ต้อง download เพิ่มเติม

ลองดูตัวอย่าง program
เริ่มด้วยการ start ring server
เพื่อให้ distribute process ใช้เป็นศูนย์กลางในการเชื่อมต่อ

require 'rinda/ring'
require 'rinda/tuplespace'
 
DRb.start_service
 
ts = Rinda::TupleSpace.new
place = Rinda::RingServer.new(ts)
 
DRb.thread.join

จากนั้นก็ โปรแกรมที่รับ input เป็น matrix แล้ว split ข้อมูลเป็นงานย่อยๆ
ในตัวอย่างนี้ก็คือการคูณกันระหว่าง m1 กับ m1
(เพื่อให้ algorithm ง่ายขึ้น
เราแอบช่วยด้วยการทำ transpose matrix บนตัวคูณก่อน)

require 'rinda/ring'
require 'rinda/tuplespace'
 
class Splitter
 
  def initialize
    DRb.start_service
    @ts = Rinda::TupleSpace.new
  end
 
  def run(m1,m2)
    puts "start"
 
    rp = Rinda::RingProvider.new :MTX, @ts, 'matrix multiplication'
    rp.provide
 
    count = m1.size * m2.size
    @ts.write([:outstanding, count])
 
 
    (0 .. m1.size - 1).each do |i|
      (0 .. m2.size - 1).each do |j|
        puts "write i=#{i}, j =#{j}"
        @ts.write([:map, i, j, m1[i], m2[j]])
        count -= 1       
        @ts.write([:outstanding, count])       
      end
    end
 
    DRb.thread.join
  end
 
end
 
m1=[[1,2,3],
    [4,5,6],
    [7,8,9]]
Splitter.new.run(m1,transpose(m1))

map function

require 'rinda/ring'
require 'rinda/tuplespace'
 
class Mapper
  def self.run
    DRb.start_service
    new.solve
  end
 
  def initialize
    ts = Rinda::RingFinger.primary.read([:name, :MTX, DRbObject, nil])[2]
    @ts = Rinda::TupleSpaceProxy.new ts # for safety
    puts @ts
  end
 
  def solve
    loop do
      tmp = @ts.take([:map, nil, nil, nil, nil])
      @ts.write([:reduce, tmp[1], tmp[2], calculate(tmp[3],tmp[4])])
    end
  end
 
  def calculate(v1, v2)    
    v1.zip(v2).inject(0) do |sum, tmp|
      sum + (tmp[0] * tmp[1])
    end
  end
end
 
Mapper.run

สุดท้ายก็ reduce process
(ขี้เกียจเขียนเหมือนเดิม ก็เลย fix ค่า dimension ของ matrix ไว้)

require 'rinda/ring'
require 'rinda/tuplespace'
 
class ReduceMap
 
  def initialize(rows,cols)
    @result = []
    rows.times do |_|
      @result << ([0] * cols)
    end
    ts = Rinda::RingFinger.primary.read([:name, :MTX, DRbObject, nil])[2]
    @ts = Rinda::TupleSpaceProxy.new ts # for safety
    puts @ts
  end
 
  def run
    loop do
      tmp = @ts.take([:reduce, nil, nil, nil])
      puts "i = #{tmp[1]}, j = #{tmp[2]}, value = #{tmp[3]}"
      reduce(tmp[1],tmp[2],tmp[3])
      finish = @ts.take([:outstanding, nil]).last
      return self if finish == 1
    end
  end
 
  def reduce(i,j,value)
    @result[i][j] = value
  end
 
  def dump
    @result.each do |rows|
      rows.each do |col|
        print "#{col},"
      end
      puts ' '
    end
  end
 
end
 
DRb.start_service
ReduceMap.new(3,3).run.dump

เวลาทดลอง code ก็เปิด terminal ขึ้นมาสัก 5 หน้าจอ
start ringServer 1 จอ
start map function สัก 2 จอ
start reduce process สัก 1 จอ
สุดท้ายก็ start splitter เพื่อให้เริ่ม feed ข้อมูล

‹ แปลง xml (cn140 in ruby) Rails 1.2 Performance ›
»
Submitted by veer on 26 January, 2007 - 22:21.
veer's picture

อลังการ :-D

MapReduce ที่ว่าดังๆ ผมก็พึ่งรู้จัก -_-'

»
Submitted by sugree on 26 January, 2007 - 22:57.
sugree's picture

โอ้ distributed matrix multiplication แบบ ruby

rinda มันติดต่อกันยังไงครับ

»
Submitted by veer on 29 January, 2007 - 00:50.
veer's picture

rinda เหมือนเป็นตัวมาครอบ drb อีกที แล้วก็ไป bind method ที่ถูกต้องให้โดยไม่ต้องมาแยก 1 method 1 url แบบในอดีต หรือเปล่า?

โดยการรอรับ boardcast udp แล้วก็ตอบกลับไป หรือเปล่า?

(ตอบสร้างกระแสไปก่อน รอคนมาแก้)

»
Submitted by pphetra on 30 January, 2007 - 10:40.

พึ่งหัดใช้เหมือนกัน
เลยต้องไปหาคำตอบมา


rinda เข้าใจว่า ล้อมาจากคำว่า Linda
ซึ่งเป็น research project เกี่ยวกับ parallel programming environment
ของ Yale University และเป็น commercial product ด้วย
http://heather.cs.ucdavis.edu/~matloff/Linda/NotesLinda.NM.html


หลักการที่สำคัญของ Linda
ก็คือ tuple space ซึ่งใช้เป็นพื้นที่สำหรับ comunicate ระหว่าง process
process สามารถ post และ read message จาก tuple space ได้
(ใน code จะเห็นผมใช้ตัวแปรชื่อ @ts สำหรับ tuple space)
หลักการนี้ ถูกใช้ใน Jini/Javaspaces ด้วยแฮะ นี่ก็พึ่งรู้


การ fetch ข้อมูลจาก tuple space จะใช้หลักการ pattern matching
ใน code จะเห็นว่า เราใช้ nil แทนการ map เข้ากับอะไรก็ได้


ข้อระวังอย่างหนึ่งของการใช้ tuple space ก็คือ
มันไม่ ordered สิ่งที่ใส่ก่อน อาจออกมาทีหลังได้



»
Submitted by pphetra on 30 January, 2007 - 10:46.

ของ python เห็นมี PyLindaด้วย

»
Submitted by sugree on 30 January, 2007 - 13:27.
sugree's picture

อืม มันคือ message passing แบบนึงนี่เอง

»
Submitted by veer on 30 January, 2007 - 17:32.
veer's picture

สมกับที่รอคอย ;-)

»

ย้าย Codenone

ประกาศย้าย Codenone ไปใช้ Forum ของ Blognone แทนครับ ตามไปตั้งกระทู้ต่อได้ที่ Codenone Forum (รายละเอียดอ่านจากกระทู้ ย้าย Codenone ไปรวมกับ Blognone)

กระทู้เก่าๆ จะย้ายตามไปในภายหลัง ตอนนี้ปิดการโพสต์กระทู้ไว้ เหลือไว้เฉพาะอ้างอิงเท่านั้น