Tham dự Tech Lounge

Tham dự Tech Lounge


GraphChi, phần mềm mới cho phép phân tích khối lượng dữ liệu cực lớn trên PC

uhraman
17/7/2012 17:42Phản hồi: 24
GraphChi, phần mềm mới cho phép phân tích khối lượng dữ liệu cực lớn trên PC
Các doanh nghiệp công nghệ thông tin và các nhà khoa học/kỹ sư thuộc lĩnh vực tính toán vừa có một tin vui về nghiên cứu trong lĩnh vực khoa học máy tính và tính toán. Mới đây, một nhóm các nhà khoa học tại Select Lab, đại học Carnegie Mellon, vừa xây dựng thành công một phần mềm mới có tên GraphChi cho phép thực hiện các tính toán liên quan đến những khối lượng dữ liệu cực lớn (ví dụ như phân tích của công cụ tìm kiếm hay mạng xã hội) ngay trên một chiếc máy tính cá nhân hay laptop thông thường. Được biết trước kia để xử lý các công việc dạng này người ta cần phải dùng đến các cluster máy tính/siêu máy tính rất lớn, như dịch vụ đám mây EC-2 của Amazon chẳng hạn.

Graph Computation và GraphChi
Trước tiên, cần phải nói rõ rằng GraphChi không phải là một giải pháp toàn mỹ cho mọi công việc tính toán nặng nề. Thực tế, phần mềm được thiết kế để sử dụng cho các tính toán liên quan đến Graph Computation. Tuy nhiên, đừng vội coi thường nó, Graph Computation đã và đang không ngừng tăng lên về số lượng và đóng vai trò cực kỳ quan trọng trong thời đại hiện nay.

Vậy Graph Computation là gì và tại sao lại bảo nó quan trọng? Hiểu qua ví dụ có lẽ là phương tiện nhanh và dễ hình dung nhất trong trường hợp này. Ta hãy bắt đầu với một chức năng của Facebook, Top Post. Bạn có biết để đưa ra được post nào là top đối với bạn, Facebook đã phải phân tích đống dữ liệu khổng lồ và phức tạp liên quan đến mối liên hệ giữa các tài khoản/status/comment... khác nhau? Vâng, đó chính là Graph Computation - các tính toán liên quan đến khối lượng lớn dữ liệu và mối liên hệ qua lại giữa chúng. Vậy chúng có quan trọng không? Câu trả lời chắc phần lớn anh em đây đều đồng ý với mình là "Có".

Không chỉ có vậy, GraphChi còn có khả năng xử lý các “streaming graph”, một loại Graph Computation liên quan đến việc mô hình hóa các mạng lưới thông tin lớn một cách chính xác bằng cách chỉ ra sự thay đổi mối liên hệ giữa các dữ liệu theo thời gian. Thông tin không chỉ được xét trong sự tương tác qua lại tại thời điểm hiện tại mà cả với những gì trong quá khứ. Quả là một khối lượng công việc khổng lồ mà ai cũng nghĩ chỉ dành cho siêu máy tính/cluster mà nay lại có thể thực hiện trên chiếc PC của bạn, thật tuyệt vời.

Nguyên tắc làm việc của GraphChi
Để tính toán nhanh, các máy tính trong các hệ thống thông thường đều phải lưu chúng lại trong RAM. Với Graph Computation, rõ ràng RAM của một PC không đủ để lưu lại toàn bộ thông tin cần thiết. Ổ cứng thì khác, với sự phát triển của công nghệ lưu trữ thì dung lượng của thành phần này trên PC hiện nay đủ khả năng để làm điều đó. Tuy nhiên nhược điểm của ổ cứng là tốc độ đọc và ghi dữ liệu của chúng chậm hơn RAM nhiều do đó ảnh hưởng đến việc xử lý các Graph Computation và người dùng buộc phải đưa chúng lên các hệ cluster/siêu máy tính. Để giải quyết vấn đề này, Aapo Kyrola, một thành viên trong nhóm nghiên cứu, đã xây dựng một thuật toán truy xuất ổ cứng “ít” ngẫu nhiên hơn*, nhanh hơn và tối ưu cho Graph Computation để khắc phục nhược điểm của ổ cứng trong các tính toán liên quan. Giải thuật này chính là linh hồn trong phần mềm mới GraphChi.


Và tính hiệu quả của GraphChi...
Carlos Guestrin, đồng điều hành của Select Lab, cho biết sử dụng một chiếc Mac Mini chạy GraphChi, họ có thể phân tích các social graph (graph computation liên quan đến mạng xã hội) của Twitter từ năm 2010 với khoảng 40 triệu người dùng và 1,2 tỉ kết nối liên quan trong 59 phút. Một kết quả đã được xuất bản trước đó cho biết để xử lý lượng tính toán này cần phải mất 400 phút với hệ thống cluster gồm 1.000 máy tính kết nối với nhau, tức tương đương khoảng 400.000 phút = 6.666 giờ = 278 ngày tính cho một máy tính nếu làm việc một mình.

GraphChi và một số lĩnh vực ứng dụng
Rõ ràng với sự tiến bộ trong các phân tích liên quan đến Graph Computation, các sản phẩm mới liên quan đến web sẽ phát triển hơn, tỉ như tìm kiếm tài liệu, quảng cáo trên mạng, công cụ dẫn đường... thậm chí cả an ninh mạng (phân tích mối quan hệ và tìm kiếm tội phạm/tổ chức tội phạm...). Với GraphChi, các lập trình viên/chuyên viên chỉ cần sử dụng máy tính cá nhân để xử lý dữ liệu thay vì phải viết chương trình chuyên dụng cho các hệ máy tính rồi tốn công chờ đợi đến lượt của mình.

Một lĩnh vực khác liên quan đến nhiều tính toán Graph Computation đó là y sinh học, sinh học tính toán hay khoa học vật liệu. Trong y sinh học, cách thức bộ não làm việc hay liên kết các bản ghi thông tin bệnh nhân để xác định chính xác bệnh đều liên quan đến graph computation. Trong sinh học tính toán, hay khoa học vật liệu việc mô phỏng các DNA, protein, hệ tế bào, các quá trình chuyển pha của vật liệu... đều phải viện đến các tính toán phức tạp với lượng lớn dữ liệu trong quá trình xử lý cũng như kết quả cuối cùng.

Thay cho lời kết
“Lớn” chỉ là một khái niệm tương đối khi có một vật mốc làm chuẩn. Tuy không thể phủ nhận tính cần thiết của các cluster máy tính/siêu máy tính nhưng trong thực tế nhiều dữ liệu “không quá lớn” như những gì người ta hình dung. Những công cụ như GraphChi sẽ cho phép các công ty/cá nhân linh hoạt hơn, tiết kiệm hơn, nhanh chóng hơn và tiện lợi hơn trong các vấn đề liên quan đến tính toán Graph Computation. Hy vọng tương lai chúng ta sẽ còn thấy nhiều nghiên cứu hữu ích như thế này hơn nữa.

Các bạn quan tâm có thể vào trang web của dự án và của Select Lab để tìm hiểu thêm.

Quảng cáo


Nguồn: TechnologyReview
24 bình luận
Chia sẻ

Xu hướng

mung we co phan mem xai
smartphones
ĐẠI BÀNG
12 năm
Mù tịt @@
lại đứng thứ 2 😔
@www.facebook.com/laptopsv hàng 3 lận 😆
quanqw
TÍCH CỰC
12 năm
Cách này trước mình cũng có ý tưởng như vậy nhưng không đủ trình làm được như mấy anh này.
Một phát minh mới đầy triển vọng cho khoa học... hi vọng sớm có bản dùng thử cho ae ta cùng trải nghiệm...😃
Cái này cao siêu quá, mình với không tới, hic....
firestork
TÍCH CỰC
12 năm
thế định dùnng làm việc gì?:eek:
quanqw
TÍCH CỰC
12 năm
@firestork Thuật toán thành công rồi thì áp dụng vào hầu như mọi chương trình máy tính hiện nay. Ví dụ Windows 7 yêu cầu ram 1G, cpu ít nhất từ pentimun gì đó trở lên thì nếu thay đổi theo thuật toán này có thể giảm đi tới mức ram cần khoảng 100-200 MB cpu cần có thể ít hơn ....
Rất nhiều việc bác àh. Đừng nghĩ mọi thứ cao siêu và xa vời quá. hãy đơn giản nó đi 1 chút....
Với em pm này có thể để tính toán độ phức tạp của 1 bài toán để có phương án tối ưu nhất, hoàn hảo nhất.... em học IT nên phải lập trình và viết rất nhiều các bài toán về lập trình.... hoặc cũng có thể áp dụng các thuật toán người ta xây dựng sẵn để trau dồi khả năng tư duy thôi... nói chung là nhiều lắm.
=>Chốt lại 1 điều là các nhà khoa học cũng đã nghĩ chán rồi mới xây dựng cái này chứ không phải làm ra để khoe mẽ khả năng của mình bác ạh...😁
Cái này mà để tính toán lượng tử thì hay biết mấy.

Mình cứ tưởng có link rồi. hik
quanqw
TÍCH CỰC
12 năm
@sizuki2011 Cái này liên quan gì đến tính toán lượng tử bạn.
lendras
TÍCH CỰC
12 năm
Mã nguồn mở, há há... Phải lôi cái thuật toán truy xuất ổ cứng ra nghiên cứu thôi =p~
doki
ĐẠI BÀNG
12 năm
Với khối lượng dữ liệu:
Gần 640 Terabyte lưu lượng truy cập đang được chuyển giao từng phút bởi các mạng IP toàn cầu; 6.000.000 Facebook views; 2 triệu truy vấn tìm kiếm Google; 30 giờ video được tải lên YouTube, và 1,3 triệu video được xem.
thì phân tích dữ liệu quả thật là quan trọng đối với nhiều lĩnh vực trong thời đại thông tin ngày nay.
Có lẽ đang trong giai đoạn thử ghiệm nên chưa thể download được. em nghĩ người ta sẽ xây dựng thêm các thuật toán cho các nghành khác nữa đấy vì Vật lý là 1 lĩnh vực cần tính toán rất nhiều mà...
@cool_boys Code này, có cả sản phẩm demo luôn. Thuật toán phát triển xong rồi, có hướng dẫn sử dụng rồi chứ thử nghiệm gì nữa.
https://code.google.com/p/graphchi/
công nghệ cangd phát triển thì hiệu quả sẽ càng tăng, đó là quy luật rồi.
Mấy cái FOSS phải đọc kĩ giấy phép, dùng lung tung có ngày bị kiện =))

Lại thêm 1 bác đọc qua qua xong phán.

Cái này chỉ hiệu quả với các thể loại bài toán đồ thị và những thứ đồ thị hóa được.
quanqw
TÍCH CỰC
12 năm
Bạn đọc kĩ lại đi rồi phán.
Tôi nói đến thuật toán chứ không nói về phần mềm.
Bạn không tô đậm nốt phần sau?

Tôi đang nói đến cái thuật toán đó chỉ đảm bảo tối ưu cho Graph Computation, ai đảm bảo nó tốt cho những thứ khác? và ai đảm bảo tất cả mọi thứ có thể quy về Graph Computation? Mà bạn biết câu Program = Data Structures + Algorithms không vậy?
quanqw
TÍCH CỰC
12 năm
@Spirit Coder Nhưng đoạn bạn trích có nói là nó chỉ dành cho Graph Computation đâu, ở dưới còn có nhiều ứng dụng cho nhiều loại dữ liệu khác nữa cơ mà. Với lại đây là thuật toán truy xuất ổ cứng chứ có phải xử lý dữ liệu đâu mà bạn nói là chỉ dùng cho Graph Computation.
@quanqw Tên cái phương pháp người ta dùng là "Parallel Sliding Windows" và mình search vòng vòng chả thấy chỗ nào chỉ ra đó là thuật toán truy suất ổ cứng cả. (trừ cái bản dịch này)

Bạn quote nốt nó áp dụng được cho những loại dữ liệu gì? Trong bài báo này thì mình thấy thêm mỗi cái streaming graph còn google thì thêm cái để phân tích ADN từ năm 2010.

Edit: đúng là PSW không phải chỉ dành cho Graph Computation nhưng nó cũng chả phải thuật toán truy suất ổ cứng, nó chỉ là 1 cách người ta dùng để bơm dữ liệu vào cho chương trình thôi, thay vì đưa từng tí một vào thì đưa cả 1 khối vào -> giảm random access. Cái này các OS đặc biệt là Linux đã làm rất tốt qua việc cache lên RAM rồi.
quanqw
TÍCH CỰC
12 năm
@Spirit Coder Cảm ơn thông tin, mà bạn có chắc là nó đã có trong linux không.
@quanqw Mình nói chỗ đó không rõ, ý mình là Linux có những thuật toán cache tốt để giảm random access lên HDD 😁 (tận dụng RAM).

Thêm thông tin: GraphChi đã được test trên Linux, Mac, chưa được test trên Windows (chắc tác giả thấy không cần)

Xu hướng

Bài mới









  • Chịu trách nhiệm nội dung: Trần Mạnh Hiệp
  • © 2024 Công ty Cổ phần MXH Tinh Tế
  • Địa chỉ: Số 70 Bà Huyện Thanh Quan, P. Võ Thị Sáu, Quận 3, TPHCM
  • Số điện thoại: 02822460095
  • MST: 0313255119
  • Giấy phép thiết lập MXH số 11/GP-BTTTT, Ký ngày: 08/01/2019