11 months ago

我們決定先從自幹一個能自動放杯子的機器開始,姑且就稱之為自動落杯器吧。但我對於機構設計一竅不通,先前完全沒有任何相關經驗,於是只好先從模仿開始。我們上網找了一個按下按鈕,就能夠自動落下紙杯的機構,如下圖

Read on →
 
11 months ago

自動飲料機的概念相當簡單,你一定喝過CoCo、五十嵐、清心等手搖飲料。那些飲料都是工讀生做的,手搖飲料的工序相當固定,加茶、加糖、加冰塊,搖一搖就解決了。要是我們可以做一台機器,只要按個按鈕,封好膜的飲料就會自動跑出來,那是多棒的一件事啊,如此一來人力成本就可以下降,我們也可以收到錢,商業模式簡單又直覺。

會想到這個點子是因為大三時,我曾和校園附近的飲料店合作過,不僅幫忙架設網站,還做了一款飲料DIY的行銷活動,讓學生可以在網站上調製自己喜歡的飲料,並到店內購買,當時這個活動相當有趣,算是某種類型的O2O模式,用線上活動帶動線下消費,吸引許多學生到店內購買自己發明的特調。

Read on →
 
11 months ago

這是一篇回顧文,故事發生的時間點在2014年底~2016年初,當時發生太多事情,故事太長而一直沒有動筆,最近快要當完兵,便整理以前的資料和照片,把過去那段瘋狂的往事記錄下來,謹以這個故事獻給那些試圖打開真理之門的人們,或許回過頭看一切都是徒勞,但只要能夠再站起來,就能抵達任何地方。

人不付出犧牲,就得不到任何回報。如果要得到什麼,就必須付出同等的代價,這就是鍊金術的基本原則,等價交換。當時我們深信著,這就是這世界的真理。------《鋼之鍊金術師》


這是一個充滿汗水與血淚的故事。

那年我大四,22歲,是個翅膀還沒硬就想要改變世界的年紀。

Read on →
 
about 1 year ago

最近在研究影像處理,在思考照片中的物體,會如何隨著相機拍攝的角度改變而變形。因此產生了一個有趣的疑問:為什麼照片中的透視點能夠連成一條線?


圖片引用自DesignByFoot blog

可以看到上圖中,不論是地上的抽屜、櫃子,只要將平行線的兩端延伸,最後就會交於一點,而這些不同平行線延伸出的交點,最後竟然會交於同一條水平線上,我覺得這實在是太神奇了,不禁好奇為什麼會有這個現象?

這個問題看似簡單,其實並不好思考。我想說學設計的應該會對透視比較了解,所以問了幾位學設計的朋友,他們其實也不太會解釋為什麼,就說是一種FU(馬的到底是什麼FU啦XD),我看了好幾篇文章,有設計的、也有計算機圖學的,平常在走廊走路時像怪人一樣不斷的看天花板無限延伸的平行線發呆,想了幾天,才總算搞懂這是怎麼一回事。

什麼是透視?

這裡的透視不是透明的意思,而是一種投影的現象。其實你每天張開眼睛,看到的畫面通通都是透視圖。無限延伸的鐵軌會在遠方交於一點是最經典的例子。

這是個很有趣的現象,現在想像假設地面上有不只一條的鐵軌,通通朝正前方延伸,有一個很重要的現象是,這些鐵軌通通會交於一點。

會這樣

而不會這樣

同樣地,如果我們從高空俯視大樓,會發現所有的牆壁邊線無限延伸後,都會交於同一點。

上面這三張圖都出自巴哈姆特 Arrogant(傲慢的羊)寫的透視教學,他的文章是針對繪畫的透視做介紹,是我目前看來最清晰易懂的教學,相當推薦

這個現象很直觀,我們可以從這裡切入,第一個要思考的問題是,為什麼會有這個現象?

攝像機模型

讓我們用更具體的模型來觀察透視現象。


圖片出自the university of edinburgh

所謂的透視,就是將三維世界座標系的物體,投影到某個平面上的現象。可以看到上圖的原點代表投影中心,投影中心前方有一個平面。而所謂的投影,就是將三維世界的物體,和投影中心連成一線,交於該平面上產生的圖樣。


圖片引用自Wiki Vanishing Point

現在我們將剛剛的延伸的鐵路,透過這個攝像機模型來表示,上圖可以看到隨著鐵軌的延伸,遠方的鐵軌和投影中心的連線越來越接近平行地面的直線,最後那個無限遠的點,其實就是一條由投影中心發出,平行於鐵軌方向的直線,交於平面上的點

推廣到不同角度的鐵軌

現在,想像另一種情況。假設這個鐵軌不是往正前方無限延伸,而是例如朝右45度無限延伸,那麼他會交於圖片上哪一點?

圖都找給你看了,答案很明顯吧。會在偏右的位置。

如果用剛剛所提的,這個點其實會在一條由投影中心發出,平行於該偏右鐵軌的直線,交於平面上的點


自己畫的廢廢手繪圖

注意我講的偏右的意思是,你的視線朝正前方看,此時腳下的鐵軌往右偏。你的視線往前看,但用眼角餘光觀測鐵軌,發現鐵軌的盡頭位於整個視野中偏右的位置。如果你轉個身,讓視線和鐵軌朝同一個方向,那麼鐵軌的無限遠處自然就在視野的正中央了。

現在我們得到一個非常重要,基本上是整個透視投影界(?)最重要的觀念:所有同樣方向平行線的無限遠處,會落在投影平面上的同一點

所有朝正前方平行的鐵軌的無限遠處會落在同一點,所有朝右方45度平行的鐵軌的無限遠處也會落在同一點。而這些點都被叫做消失點,而消失點的座標恰好是一條從投影中心發出,平行於該鐵軌方向的直線,落在投影平面上的點。

為什麼這些透視點會連成一條線

掌握這些觀念後,現在我們要回答本文一開始的問題:為什麼這些透視點會連成一條線?

因為這些不同方向的鐵軌(或物體)都平行於地面,因此從透視中心發出到無限遠處的射線也會平行於地面。他們可能有不同的方向,朝正前方的鐵軌的消失點在正前方,偏右的鐵軌消失點在偏右的地方,但是無論是哪個方向的鐵軌,從透視中心延伸到投影平面上消失點的射線都平行於地面,因此他們都在同一個高度上,成為一條由消失點構成的水平線。

看看一開始的圖,不論是地板上的抽屜、櫥櫃裡的抽屜、櫥櫃本身的邊邊,這些平行線在三維空間中通通都平行於地面。因此這些平行線的消失點會落在照片上同一條水平線上。

換句話說,要是該平行線組並沒有平行於地面,那麼他的消失點就不會落在該線上。舉例來說像下圖,V1和V2這兩個消失點會在同一條水平線上,是因為空間中朝向V1, V2方向的平行線平行於地面。而斜屋頂的消失點V3因為不平行於地面,所以消失點不會在V1和V2的連線上。

那位什麼V3, V1, V4會在同一條線上呢? 因為這些的平行線雖然方向不同,但都平行於該房子的左面,所以他們的消失點會落在同一條線上。


圖片出自HSUEH Gallery

一點透視是個假議題

想通了這一點後,你會發現,大家平常在說的一點透視、二點透視、三點透視,通通都是假議題。

所謂的一點透視,只是剛好圖片適合用一組最有代表性的平行方向來畫


圖片出自GCS ARTS

兩點透視,只是剛好圖片適合用兩組最有代表性的平行方向來畫


圖片出自D'source

三點透視

思考的關鍵在於,你的投影中心、投影平面,和整個三維世界的連線。只要記得大原則「所有同樣方向平行線的無限遠處,會落在投影平面上的同一點」,其他就可以一一推導出來。

網路上大部分談透視的文章都是繪畫類型的,用作畫的角度來看透視,另外一小部份是計算機圖學的類型,用矩陣和齊次座標系來看透視。要用簡單的方式把透視的觀念講清楚,我覺得不是件很容易的事情,昨天把這個想法告訴朋友,他們都有種醍醐灌頂的感覺,故寫成文章以茲紀念。

 
about 1 year ago

咪娜桑拍謝啦,這個Blog的名字和網址都改了。

當初這個Blog叫Enginec,是因為我的名字發音很像Engine,但Engine這個詞實在太常見了,於是在結尾加一個c作為識別。

但用了一段時間後發現,這個詞實在是不太好搜尋,發音也不好發音(到底要唸成Engine-C還是Engine-nic),考量許久後,決定趁影響還不大明明是還沒有什麼影響力以前換名字啦。

之後會以Opass的身份繼續發表文章,背後還是同一個人請放心。

 
about 1 year ago

人生何處不迷茫

前一陣子,我再度對未來陷入了迷茫,甚至到了有點輕度憂鬱的地步。

茫然的因素主要有三個,一個是我對系統程式找不到成就感。另一個是對台灣資訊產業的悲觀。最後一個是金錢的問題。

剛離開成功嶺,開始服替代役時,我那時不斷問自己,未來想走什麼領域。我寫過幾個網站、做了一台飲料機,入伍前還上完Andrew Ng的機器學習線上課,最後我決定去找Jserv研究系統程式。

最後會決定系統程式的原因是有脈絡的,我不想繼續寫網站,大學期間我寫了三年網站,前端的技術更迭太快了,我努力了三個月才上手的AnglarJS很快就過時,JS邁向ECMA6,react.js當紅,之後又來個vue.js,我在乎的是解決眼前的問題,做出我想要的東西,而不是一直追網站的最新技術。

我覺得做網站能解決的問題有限,又不想當個接案者。於是我就跑去弄硬體,大四那年我花了一年的時間搞了一台自動做手搖飲料的機器,這個專案讓我深刻理解,現實世界的問題的難度不太可能靠一個人攻克,跨領域合作和專業化分工是必然的結果。

上完Andrew Ng的機器學習課,我曾一度考慮要不要研究Deep Learning。但後來讓我卻步的理由是,目前Deep Learning的發展方向還很亂,而且就像是個黑盒子一樣,it just works but we don’t know why。而且台灣做深度學習的公司實在有限,就先把這個選項擺到一旁。

剛離開成功嶺,思考一段時間要走什麼領域後,最後我選擇向Jserv學習系統程式。當時我給自己的理由是,這個東西很基礎、很紮實,技術的變動性應該不會像網站那麼大,而且Jserv有那麼多學生畢業後都找到不錯的工作,未來跟產業界應該也能銜接。

Jserv提供了兩個題目,一個是記憶體分配的機制,另一個是程式的並行性。我花了幾個月的時間研究這兩個題目,但後來卻漸漸失去學習的動力。回過頭來看失去興趣的原因,最關鍵的因素是,缺乏短期的成就感。

研究記憶體分配是為了ARRC的火箭系統,需要一個合理的機制來分配記憶體。我們研究了幾個記憶體管理套件的分配機制,我努力告訴自己這些東西很重要,但這些東西的成就感實在是很小眾,大多數人並不會對降低的25%的記憶體碎片到興奮。

我們後來研究程式的並行性(Concurrency),這個領域沒有多少中文資料,英文的資料也很分散,我花了幾周,啃了好幾本原文書的相關章節,才大致了解背景知識,包括處理器的指令重排、快取、程式碼執行的順序。但我距離寫出一個可以使用的lock-free演算法還好遠,這東西本身是為了提昇效能而存在的,讓系統能夠跑得更快、更順,我相信這領域很重要,但是那種膚淺的相信沒辦法帶給我繼續投入的動力。

在心情鬱卒的那段日子,我常常上104和ptt科技版,看看未來能從事什麼相關的工作。結果上頭充斥著各種薪水不上不下、工作十年也沒什麼前景的工作,只有少數幾間外商、厲害的公司才端得出稍微像樣的牛肉來。科技版上頭各種悲觀的仇恨發言,只求爽、只求有錢賺,不求進步的價值觀,看久了心情都會受到影響。

我才更明確的意識到,這是整個產業的問題。如果公司沒辦法做出有價值、有技術差異、能夠甩開競爭對手的產品,最後就會陷入低價競爭的迴圈當中,最後公司賺不到錢,員工也不會成長進步,大家比誰加班比較多,看起來比較努力而已。

同一時間,我手上的各種3C產品的折舊也漸漸到期了。我的筆電已經用了六年,開始會不定期過熱,鍵盤也開始鬆脫。因為沒錢所以先墊著用的ASUS手機時常會讀不到sim卡、網路連不上要重開機,頻率高到惱人的程度。鞋子破了、衣服舊了、眼鏡鏡片也早已磨損到會影響心情的地步。但我只是個薪水6000塊的役男,在台北等級消費下,光是伙食費就入不敷出。這些揮之不去的因素像夢魘一樣,不斷的侷限我思考的可能性。

負面情緒的迴圈

我突然理解憂鬱症是怎麼一回事。你向罹患憂鬱症的病人說看開點是沒有用的。因為現實把他所有可能性都封死了。他會陷入一個負面的迴圈,因為沒有錢,於是找工作的時候錢變成很重要的因素,但大多數的職缺薪水都不高,發展性也堪慮。而且如果把錢放到第一順位,你便無法傾聽內心真正想要的工作是什麼。這些道理憂鬱症的人都知道,他很努力的想要傾聽自己內心的聲音,但外在的惡劣的產業環境不斷的干擾他的思考,我該寫driver嗎?但driver是個枯燥乏味的工作。我該去系統廠嗎?但每個人都說系統廠是屎缺。還是該選比較高薪的外商?但外商大多數的工作是作客戶支援,並不是個長久之計。Jserv的包袱依舊掛在身上,他覺得自己不去學系統程式彷彿背棄了老師對自己的期望,但缺乏成就感的學習方式讓他無法繼續前進。

更糟糕的是,一旦這樣的負面想法持續超過一週,腦袋裡的某些神經迴路似乎會定型下來。你的思考會開始往悲觀的方向走,因為缺錢,所以變得更不敢投資自己,到書店連要不要買一本書都會猶豫半天。錢本身是帶來更多可能性的工具,但因為缺錢,不敢花錢,你等於是把大半的可能性都封死了。你不斷想找未來工作的方向,比平常變得更現實、更功利,但這不是好事,過於現實、悲觀會讓你看不到未來的希望,嘗試把一切怪罪在環境上,急功近利讓你無法做更長遠、短期內無法帶來回報的投資。

幸好兩三週之後,我總算脫離低潮與悲觀的負面迴圈,我試著整理出一些我自己的作法:

  • 運動,我在低潮這段時間依然繼續保持著重訓的習慣。一週將近4~5次,運動時大腦會分泌腦內啡,產生愉悅感,抵銷一部分的負面情緒,不讓其無上限的繼續累積。
  • 和朋友聊聊,線上或約出去吃個飯都好
  • 出去玩耍,脫離現實,我和朋友跑去馬拉灣玩水、跑去烏石被浪衝、跑去龍洞跳水

上述是較為消極作法,目的是避免情況惡化,但這些對於解決問題並沒有太大的助益。要脫離負面迴圈,我認為最有效的作法是

  • 中斷惡性循環,花一筆大錢在你目前最需要的地方上。
  • 找一個發自內心相信、並且願意投入努力的目標去實踐

脫離省錢的惡性循環

這樣的日子持續數周後,某天起床,我的內心突然浮現一個聲音:「不能再這樣下去了,我必須趕快把眼鏡換掉。」後來我去找了專業的配鏡店,配了一副上萬元的眼鏡。

戴上新的眼鏡後,透過毫無刮痕的新鏡片看世界,整個世界都光輝起來。每時每刻抬起頭來,都可以重新感受到世界的美好。但比起眼前的光明,更重要的是內心的轉變。你知道戴在你鼻樑上東西很貴,他不斷在提醒你,你是有價值的,你值得這些,你會意識到,自己該重新展開新的人生,思考新的可能性。

花錢的目的,並不是讓你大玩特玩,像壓力很大的上班族週末跑去百貨公司血拼轉移注意力。花錢真正的目的,是為了體驗投資自己帶來的好處,讓自己不要因為怕窮而省錢,結果越省越窮。穿一件用料好的衣服,讓自己出門時充滿自信、戴一副清澈明亮眼鏡、換掉那台sim卡常常接觸不良、鏡頭模組爛到根本不會想拿來拍照的ASUS手機。花錢只是手段,真正的目的是消除那些生活中帶來負面情緒的因素。

低潮是反省的好時機

在低潮的期間,我依舊不斷的反省,過去所做的決策與判斷,哪些是因為正確的觀念而產生好的結果,哪些想法是有問題的。

  • 追尋穩定的技術而跳去系統程式錯誤的觀念(但這不代表跳到系統程式是錯誤的),每個領域的技術都會不斷進步、演變,網頁也是、系統程式也是。真正的問題不是在技術變得太快,而是你沒有找到願意投入十年的方向
  • 認清你的失敗,是因為方向錯誤,還是方法錯誤。所謂的方向錯誤,是你本身就不適合、不喜歡、不該做這件事情,就像矮冬瓜跑去打籃球一樣。而方法錯誤,是你用錯方法,導致你在學習的過程中,充滿挫折。錯誤的方法包括找一堆書來讀,卻缺乏實做經驗、欠缺成就感等。
  • 把尋找目標這件事情當成一個長期的過程,請找到自己的內在動機,因為它們往往比外在動機更能長久。

人的內心其實相當複雜、難解,而且常常會自我矛盾。願意投入一件事情的理由,往往是許多不同的因素揉合在一起的結果,例如我決定投入系統程式這件事,其實包含了「我不想一輩子寫應用,我想知道我還能做什麼」、「理解電腦的底層原理好像很重要,這樣就可以活在工程師的鄙視鍊最上層」、「我很敬佩Jserv」、「感覺台灣產業需要這樣的人才」、「我覺得我的個性蠻踏實、有毅力的,應該可以勝任這樣的題目」。

但你看也知道,這些理由多半是自己內心的投射和想像,遇到現實很容易就直接被打臉。我們的心靈很容易被其他人所影響。賈伯斯就是這方面的佼佼者,他可以點燃工程師的熱情,把他們逼到極限來加快Mac的開機速度。厲害的業務員並不會讓你感受到他在推銷,但卻能夠讓你心甘情願掏出皮夾。心儀對象的一句話就讓你心甘情願的做牛做馬,反觀父母怎麼威脅利誘都沒有用。

有人會爭辯,幹嘛管那麼多?只要能夠驅使你自動自發努力的動機不就是好動機嗎?

不,不是的。一個顯而易見的例子是,為了錢工作的人,和為了理想工作的人,他們的表現絕對是不一樣的。過於理性的動機,例如錢多事少離家近,並沒辦法打動人心。羨慕與欽佩你的偶像,在遇到困難的時候,不見得有辦法帶你渡過難關。只是覺得「底層好像很重要」,如果沒有實際解決真實世界的問題,並不會感受何謂很重要,這樣的膚淺幻想很容易在遇到挫折時破滅。

我們往往是先透過感性下決策,最後才用理性解釋為什麼這麼做。而感性往往比理性更能夠打動人心,。你需要的是一個發自內心相信的動機,你願意學習、鑽研,不是因為背負著其他人的期望,不是因為薪水,而是像許多人一開始決定學吉他的原因一樣:「台上的人好酷,我想變得跟他一樣」。矽谷創業教父Paul Graham在如何才能去做你喜歡的事情裡談到:「不僅要做自己喜歡的事,而且是令人佩服的事,是那種做完可以說“哇,太酷了”的工作」。但不要誤會我的意思,你得先發自內心覺得很酷,進而把事情做好,才會受人尊敬,而不是為了受人尊敬,去尋找那些看起來能夠獲得聲望的工作。

每個人都是自己人生的駕駛,由自己決定開往的目的地。找到內心想前往的方向,才能夠享受旅途的美景,注意到各種有趣的機會,如果只是為了找到寶藏而前進,不斷患得患失是一件很可惜的事情。旅途中,你需要找到加油站,才能讓你的車子充滿動力,開往下一個里程碑,加油站就是你的成就感。

成就感就像油料一樣

沒有成就感的努力不會持久。為什麼大多數人沒辦法持之以恆的健身?但少數人可以練就一身好身材?因為大多數人持續了兩三個禮拜,沒看到效果,很容易就倦怠,不知不覺就放棄了。但少數人卻能夠撐過那段看不見陽光的日子。

我不願意把這件事情簡單的歸因於毅力,把那些放棄的人歸因於不夠努力。那些成功跨過無成就感之谷的人,可能是因為厲害的朋友邀約他們一起去運動,因此比較不會偷懶。前輩現身教學,幫助他們克服動作、姿勢的問題,變得比其他人更容易感受到自己的進步,遇到問題也能夠立刻修正。經過一兩個月之後,他們的身形漸漸有了改變,旁人開始稱讚,他們也掌握了常見的動作和肌肉的出力方式,他們對自己更有自信,也更願意繼續練習下去。

要失去成就感實在是太容易了,你只需要在達到自己的目標前,不斷遇到挫折就行了。例如不斷地看書,卻做不出有用的東西。不斷嘗試各種作法,但卻不知道這些作法有沒有效。把努力的對象放錯重點,鑽研一旁的小問題,你想解決的目標卻沒有太大的進展。自己一直撞牆,卻因為害羞不願意請教別人。久久看不見成果,缺乏他人的稱讚等。想要脫離這樣的循環,統統反過來做就好了。

不需要在一開始就想要把所有事情都全部搞懂。你需要經過一段時間,才會了解一個知識領域中最重要的20%是什麼,其他80%自然而然會漸漸清晰,因此不要死命的硬啃,盡可能讓你學習的過程充滿樂趣,享受旅途的風景。多多動手練習而不是看書,書只是參考資料,偶爾停下來看一下確認方向就好。最重要的是,盡快產出一些東西,你才有辦法獲得成就感,並且快速的修正。

找方向,找方法

搞清楚自己要什麼,找到正確的方向,試著釐清自己內心的聲音,哪部份的動機是基於其他人的期望,哪部份是基於自己的幻想,哪部份的動機才是最底層、最核心,最能夠打動自己的部份?用正確的方法努力,對成果有正確的期待,盡快累積成就感。不用急著擔心錢的問題,想想你那些揹著學貸的朋友還是咬著牙撐過來了。把目光從台灣的產業移開,從世界的需求思考自己的定位。把Ptt的tech_job版關掉,脫離負面悲觀的迴圈,從更高的層次去思考,找方向,找方法,才能夠看到更多可能性。

 
over 1 year ago

Memory Consistency Models

我們前面系列提及到,實際上程式在編譯與執行的時候,不一定會真的照你所寫的順序發生。而是可能改變順序、盡量最佳化,同時營造出彷彿一行一行執行下來的幻象,只要實際的結果和照順序執行沒有差別就好。

這樣的幻象要成立,在於程式設計師和該系統(硬體、編譯器等產生、執行程式的平台)達成了一致的協定,系統保證程式設計師只要照著規則走,程式執行結果會是正確的。

但什樣叫做正確?正確的意思不是保證只會發生一種執行結果,而是定義在所有可能發生的執行結果中,哪些是允許的。我們把這樣的約定稱為Memory Consistency Models,系統要想辦法在保證正確的情況下,盡可能的最佳化,讓程式跑的又快又好。

Memory Consistency Models存在於許多不同的層次中,像是組合語言跑在硬體上時,因為處理器可以做指令重排和最佳化,雙方得確保執行結果和預期相同。或者,在將高階語言轉換成組語時,因為編譯器能夠將組合語言重排,雙方也得確保產生的結果和預期一致。換言之,從原始碼到最後實際執行的硬體上,大家都必須做好約定,才會跑出預期的結果。

最直覺的約定,Sequential Consistency

在1970年代,Lamport大大就在思考這個問題了。他提出一個如今最常見的Memory Consistency Model: Sequential Consistency,並且定義如下

A multiprocessor system is sequentially consistent if the result of any execution is
the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

我們可以分成兩個觀點來看Sequential Consistency的定義,

  1. 對於每個獨立的處理單元,執行時都維持程式的順序(Program Order)
  2. 整個程式以某種順序在所有處理器上執行

Lamport的定義濃縮的很精煉,對於第一次看到的人會抓不太他想表達的重點,因為這實在是太蠢、太顯而易見了。第一點講你的程式在處理器內會照順序跑,第二個講所有處理器會以某種順序執行你的程式。你一定覺得,幹這不是廢話嗎XD

之所以會這樣覺得,是因為你一直以來都活在這樣的世界,就像活在牛頓時代以前的人,覺得拿手上的東西放開就會掉下來一樣自然。接下來我們會告訴你,想要保證這樣的現象,在現代的處理器上會限制很多最佳化的手段,讓程式執行的沒那麼快。如果你同意放棄一些約定,例如不保證每個處理單元維持程式執行的順序,我們還能榨出更多效能出來。

讓我再額外補充一點,Memory Consistency Model只是一個幻象的約定,程式執行的結果必須看起來是這樣,但是實際程式編譯完、跑在硬體上,想怎麼改變執行順序都可以,只要結果和約好的定義相同就好。

確保執行順序

我們將用這張圖來闡述Sequential Consistency的兩個要點。上圖左邊是Dekker's Alogrithm,一個關於critical section的演算法。如果我們確保Sequential Consistency,在每個處理器核心內維持program order,那麼這個程式就能確保同一時間只有一個處理器進入critical section。因為你一定是先立Flag,再檢查對方Flag是否立起,如果沒有才進入Critical Section。

但想像另一個情況,同一個處理器他可能直覺的認為Flag1, Flag2兩個變數沒有相依性,因此就算違反SC調換執行順序也沒差。如果P1和P2都先執行第二行,才執行第一行,那麼就會發生同時進入critical section的窘境。

確保對所有處理器都是一致的

上圖右邊,當P1執行A=1的效果發生後,P2進行if判斷為真,於是執行B=1,P3執行if判斷B等於1為真,最後把register1寫入A的值。這樣的程式要保證register1讀到A的值是1,前提是P1寫入共享變數A=1後,P2和P3都能保證讀到A=1,也就是確保整個程式以某種順序在所有處理器上執行,對每個處理器而言,都能看到其他先執行的指令所發生的效果。

我們接下來看三個典型的範例,就算是沒有cache的硬體架構,稍不注意也可能會違反Sequential Consistency。

Write Bufers with Bypassing Capability

這個範例會告訴我們維持Write->Read順序的重要性。


如上圖左,每個處理器都有自己的write buffer,程式在執行時處理器可以先寫到Write Buffer,晚點再寫到Memory上。

我們使用最佳化的手法,當處理器寫入write buffer時,不等待寫入到記憶體完成,直接繼續執行下面的程式。而接下來若發生read,只要讀的位址不是write buffer內等待寫入memory的位址,就允許讀取。這在單核心處理器上是個很常見的最佳化手法,不用等待耗時的寫入就繼續執行,可以縮短等待的時間。

但這種做法會導致違反Sequential Consistency,看看上圖右邊的程式,假設程式雖然看起來是一行一行執行下來,但實際上執行write時,是先寫到Buffer上,然後直接允許下一行read從主記憶體讀取。因此實際程式對記憶體的操作,會是上圖左的t1(讀取Flag2)->t2(讀取Flag1)->t3(寫入Flag1)->t4(寫入Flag2),兩個Flag都讀到0,統統進入critical section,並且違反SC。

Overlapping Write Operations

這個範例會告訴我們維持Write->Write順序的重要性。


假設在一個有多個記憶體模組,沒有bus且彼此互向連結的系統上,因為沒有bus,所以執行時不需要照順序執行,而是可以同時執行多個操作。我們假設處理器一樣照著程式的順序發出write請求,而且不等待前一個執行完畢,就直接發出下一個請求。

在執行右邊的程式時,如果遵守SC,應該可以看到Data會是最新的值2000。但這個架構上並不保證發生,因為P1寫入Data和Head時,可能會發生Head先抵達記憶體,Data後抵達記憶體的情況。因此實際的操作可能變成t1(寫入Head成功)-->t2(讀取Head為1)-->t3(讀取Data讀到舊的值)-->t4(寫入Data成功),變得完全違反SC了。

在單處理器上,對於寫入不同的位址,修改寫入的順序是不會有大問題的,只要維持data的相依性就好。但在此處的範例就可能出狀況,想要解決這樣的問題,必須等待上一個write完成之後,也就是等待acknowledgement response,才發出下一個寫入的請求。

Non-Blocking Read Operations

這個範例會告訴我們維持Read->Read, Read->Write順序的重要性。


這也是一個常見的最佳化,允許我們更改讀取的順序。假設P1很乖,程式都照順序寫入,但P2不等待read Head完成就繼續發出read Data的請求。就有可能發生t1(Read Data先回傳結果為0)-->t2(寫入Data 2000)-->t3(寫入Head 1)-->t4(讀取Head為1),產生違反SC的結果。

Cache Architechture 與 Sequential Consistency

上述三個是很典型的案例,要是程式存取記憶體的順序發生改變,可能會違反Sequentical Consistency。在有設計cache的系統內,也會遭遇上述的問題。

對於有cache的系統架構,同一份資料可能會存在於多個處理器的cache上。如果想要維持Sequential Consistency,系統要確保同一份資料在不同處理器的cache上保持一致,不然有的處理器讀到比較新的資料,有的讀到比較舊的,每顆處理器所見到的行為不一致,很容易就違反SC。就算是發現要讀取的資料剛好在cache內,也不能立刻讀出來,必須要確保前一個操作完成,才能進行讀取。

Cache Coherence and Sequential Consistency

我們需要一個機制確保不同處理器上的cache在系統中保持一致,稱之為cache coherence protocol。如果cache coherent protocal夠嚴格,那麼我們就可以保證這個系統上的程式不會出現違反Sequential Consistency的結果。

我們可以把cache coherent protocal想像成 "所有的寫入最終都會被所有的處理器看見", 以及"寫入相同的位址的順序對於所有處理器而言都是一致的"(因此寫入相同位址不會出現交換順序的情況),如果想要遵守Sequential Consistency,還要確保"寫入不同位址的順序對於所有處理器而言都是一致的"(因此所有寫入不會出現交換順序的情況)。

Detecting the Completion of Write Operations

想要維持Program Order,代表我們需要確保上個寫入完成了,才能執行下一個指令。因此我們需要從記憶體模組收到一個完成的信號代表該次寫入完成。對於沒有cache的系統來說很簡單,就從主記憶體回傳信號即可。

但對於有cache的系統,所謂的寫入完成,真正的意思是,對所有處理器而言都能看到新的寫入值,因此必需要確保每份cache都被正確的更新或是無效化(必須重新從記憶體抓正確的值出來)

Maintaining the Illusion of Atomicity for Writes

在把新的值更新到每個cache上時,要知道這樣的操作並不是atomic的,並不是一瞬間,所有的cache統統都更新完成。可能有的cache會先被更新,有的之後才更新。


如上圖,假設P1和P2都照著Program Order執行,但要是寫入A=1和A=2用不同的順序抵達P3和P4,就會發生register1和register2讀到兩個不同的值的情形。例如P3看到的是A=1 A=2 B=1 C=1, P4看到的是A=2 A=1 B=1 C=1,使得P3, P4明明是讀取相同的A值,卻出現不一致的情形。避免這種狀況的方式是確保"寫入相同的位址的順序對於所有處理器而言都是一致的"。


但只保證寫入相同位址時所有處理器都看到同樣的更新順序是不夠的。回到一開始的圖右邊的程式碼範例,P1寫入A=1,假設P2已經可見A=1,於是執行B=1,但是對P3來說,還沒收到A=1的修改,但是已經看到B=1的修改。於是便讀出A的值為0。

想要避免這種情況發生,在讀取一個剛寫入的值之前,必須要確保所有的處理器的cache都正確的更新,如此一來對所有處理器來說,整個程式的順序就一致了,就能夠滿足Sequential Consistency。

小結

這些東西說破不值錢,但對於第一次接觸Memory Consistency Model和Sequential Consistency的人而言,一開始要理解並不容易。但不用緊張看久了就有fu了,SC雖然容易理解,但其實限制了很多最佳化的手段,如果我們可以放寬對Sequential Consistency的依賴,就可以讓程式跑得更快,後續我們會往更weak的memory consistency model邁進。

Reference

 
over 1 year ago

在談論Concurrency時,常常會看到許多文件、文章使用Synchronized-with這個詞彙,但是深入google你會發現,網路上關於這個詞的資訊並不多,C++官方文件也沒有提出很明確的定義或解釋,但是他們依舊繼續使用這個詞,只說明有一些操作可以建立synchronizes-with的關係,這個詞大家並沒有給出一個很明確的定義。

我先用自己的話向大家解釋什麼是synchronized-with

synchronized-with是個發生在兩個不同thread間的同步行為,當A synchronized-with B的時,代表A對記憶體操作的效果,對於B是可見的。而A和B是兩個不同的thread的某個操作。

你會發現,其實synchronized-with就是跨thread版本的happens-before。

從Java切入

當在一個multithread的環境下,你要如何確定thread A執行someVariable = 3,那麼其他thread能夠看到3真的被寫入someVariable?

實際上,有很多原因會讓其他thread不會立刻看到someVariable為3,可能是compiler做instruction reorder,把指令重排讓程式更有效率,也可能是someVariable還在register內、或是被處理器寫到cache,但還沒被寫到到main memory上,甚至是其他thread嘗試讀取someVariable的時後讀到舊的cache資料。

因此,Java必須要定義一些特殊的語法,像是volatile, synchronized, final來確保針對同一個變數的跨thread記憶體操作能夠正確的同步。

synchronized keyword

public class SynchronizedCounter {
    private int c = 0;

    public synchronized void increment() {
        c++;
    }

    public synchronized void decrement() {
        c--;
    }

    public synchronized int value() {
        return c;
    }
}

可以看到上面的程式碼中,每個方法前面都加了一個關鍵字synchronized,這個關鍵字有兩個效果

  • Mutual Exclusive
    • 對同一個物件而言,不可能有兩個前綴synchronized的方法同時交錯執行,當一個thread正在執行前綴synchronized的方法時,其他想執行synchronized方法的thread會被擋住。
  • 建立Happens Before關係
    • 對同一個物件而言,當一個thread離開synchronized方法時,會自動對接下來呼叫synchronized方法的thread建立一個happens-before關係,前一個synchronized的方法對該物件所做的修改,保證對接下來進入synchronized方法的thread可見。

要確保這件事情,代表JVM必須要做兩件事,一個是在離開synchronized區段時,把local processor的cache寫入到記憶體內,另一個是在進入下一個synchronized前,要讓local cache失效,使處理器重新去main memory抓正確的值。這樣才能夠確保每次進入synchronized區段時,物件的狀態是最新的。

Volatile keyword

另一個常見的用法是Java的volatile,如果你將物件內的變數宣告為volatile,那麼不同thread對該變數的讀寫,保證是atomic的,而且會讀到最新寫入的值。如果我用正式一點的術語描述,就是 A write to a volatile field happens-before every subsequent read of that same volatile

thread create/join

Java在開新thread時,也會建立起跨thread的happens-before關係(其實就是synchronized-with)。當thread A呼叫Thread.start建立thread B時,thread A呼叫start之前對記憶體產生的影響對於thread B可見。

當thread A要結束時,thread B呼叫Thread.join等待thread A結束,此時也會建立起跨thread的happens-before關係,thread A結束前對記憶體的影響對於呼叫join之後的thread B可見。

圖解


這樣我們就能理解上圖了,左邊thread A確保每一行都happens-before下一行,右邊的thread B也確保每一行都happens-before下一行,因此如果我對unlock M和lock M建立了synchronized-with(跨thread的happens-before)的關係,那麼所有unlock M之前的效果,對於lock M之後都可見。

再來輪到C++

C++比Java討厭的地方在於,Java努力把各種底層的複雜性藏起來,讓上層的JVM提供一個一致的環境,得以達成Write Once, Run Anywhere的理想。但C++盡可能提供你所有你能做到的事情,即使你可能會誤用這些工具。

在2014年C++的官方標準文件(Standard for Programming Language C++)N4296的第12頁,提示了C++提供的同步操作,也就是使用atomic operation或是mutex:

The library defines a number of atomic operations and operations on mutexes that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another.

如上所述,C++定義了一系列的atomic operation和mutex,來協助你建立跨thread間的同步關係。實際上還有更多語法可用,但我們來看一個簡單的mutex例子:

#include <iostream>       // std::cout
#include <thread>         // std::thread
#include <mutex>          // std::mutex

std::mutex mtx;           // mutex for critical section

int count = 0;

void print_thread_id (int id) {
  // critical section (exclusive access to std::cout signaled by locking mtx):
  mtx.lock();
  std::cout << "thread #" << id  << "  count:" << count<< '\n';
  count++;
  mtx.unlock();
}

int main ()
{
  std::thread threads[10];
  // spawn 10 threads:
  for (int i=0; i<10; ++i)
    threads[i] = std::thread(print_thread_id,i+1);

  for (auto& th : threads) th.join();

  return 0;
}

上述的程式碼一次開10個thread,每個thread做的事情都一樣,印出傳入的參數和counter目前的值,之後把counter++。要是沒有加上mutex lock,因為thread間交錯執行,無法確保synchronized-with的關係,上個thread執行的效果無法保證傳遞給下一個thread,於是印的亂七八糟,counter數字也亂跳。

沒有加上mutex lock後果如下

thread #thread #thread #thread #12  count:  count:00

3  count:0
thread #5  count:0
thread #4  count:0
6  count:2
thread #7  count:6
thread #8  count:7
thread #9  count:8
thread #10  count:9

加上lock之後,結果就正常多了,每個thread都正確地把內容印出來

thread #2  count:0
thread #1  count:1
thread #8  count:2
thread #4  count:3
thread #5  count:4
thread #6  count:5
thread #9  count:6
thread #7  count:7
thread #3  count:8
thread #10  count:9

再次回到Synchronizes-with

實際上,要建立synchornizes-with的關係有很多種不同層次的方法,Jeff Preshing介紹Synchorinzes-with的文章內提供了下面這張詳盡的圖,這張圖只是個大致的示意,實際上可能還有其他方法可以建立同步關係。

可以看到synchronizes-with是一種跨thread間的happens-before關係,此外我們可以透過mutex lock, thread create/join、Aquire and release Semantic來建立synchronized-with關係,因為Aquire and Release是另外一個較為複雜的概念,所以我打算另外開一篇文章再來談,其餘下有更底層的C++ atomic type, memory fence和volatile types等語法,之後再來介紹。

Reference

 
over 1 year ago

我們先前談過了Sequenced-Before,現在我們來談什麼是Happens-Before

Java對Happens-Before的定義

Java的官方文件定義了什麼是Happens-Before,先不管那些volatile, synchronized等用詞,我只看最簡單的一句

If one action happens-before another, then the first is visible to and ordered before the second.

解釋的很簡單,當行為A happens-before B時,代表A的效果可見,而且發生於B之前。

通俗的解釋

讓我們用比較通俗一點的方式解釋happens-before的概念,這是由Jeff Preshing所提供的解釋

Let A and B represent operations performed by a multithreaded process. If A happens-before B, then the memory effects of A effectively become visible to the thread performing B before B is performed.

可以看到和Java的定義是差不多的,都在說明前一個操作的效果在後一個操作執行之前必須要可見。舉個簡單的例子就是

// example provided by Jeff Preshing
int A, B;

void foo()
{
    // This store to A ...
    A = 5;

    // ... effectively becomes visible before the following loads. Duh!
    B = A * A;
}

在上述的簡單的程式碼中,第一行的效果必須要讓第二行的效果可見,B才會正確的得到25,你說這不是很理所當然嗎?寫在前面一行的程式不是本來就應該先執行,之後才執行下一行嗎?

不,並不見得。

這裡有個關鍵是,Happens-before強調的是visible,而不是實際上執行的順序。
實際上程式在執行時,只需要"看起來有這樣的效果"就好,編譯器有很大的空間可以對程式執行的順序做優化。

舉例來說,像是下面的程式,

int A = 0;
int B = 0;

void foo()
{
    A = B + 1;              // (1)
    B = 1;                  // (2)
}

int main()
{
    foo();
}

如果你只下gcc file.c,產生的組語節錄如下

movl    B(%rip), %eax
addl    $1, %eax
movl    %eax, A(%rip)
movl    $1, B(%rip)

可以看到先把B放到eax,之後eax+1放到A,然後才執行B=1。

但如果下gcc -O2 file.c

movl    B(%rip), %eax
movl    $1, B(%rip)
addl    $1, %eax
movl    %eax, A(%rip)

可以看到變成先把B放到eax,然後把B=1,最後再執行eax+1,然後才把結果存到A。
B比A更早先完成。

但這有違反happens-before的關係嗎?答案是沒有,因為happens-before只關注是否看起來有這樣的效果,從外界看起來,就彷彿是先執行第一行,完成之後,再執行第二行。

因此我們學到了一個重要的關鍵,A happens-before B並不代表實際上A happening before B。關鍵在於只要A的效果在B執行之前,對於B可見就可以了,實際上怎麼執行的並不需要深究。

現在我們來看C++對happens-before的定義,其實也是相同的概念

C++對Happens-Before的定義

再來看C++的定義

Regardless of threads, evaluation A happens-before evaluation B if any of the following is true:
1) A is sequenced-before B
2) A inter-thread happens before B

在C++的解釋中,Happens-before包含兩種情況,一種是同一個thread內的happens-before關係,另一個是不同thread間的happens-before關係。

我們平常程式一行一行寫下來,我們本來就預期上一行的程式效果會對下一行的程式可見。我們先前已經清楚的解釋什麼是Sequenced-before,現在你可以發現,Sequenced-before其實就是同一個thread內的happens-before。

在跨thread的情況下,如果沒有保證happens-before的關係,程式常常會出現意料之外的結果。舉例來說

int counter = 0;

現在有兩個thread同時執行,thread A執行counter++,thread B把counter的值印出來。因為這兩個thread沒有具備happens-before的關係,沒有保證counter++後的效果對於印出counter是可見的,導致印出來的結果可能是1,也可能是0。

因此,語言必須提供適當的手段,讓程式設計師能夠建立跨thread間的happens-before的關係,如此一來才能確保程式執行的結果正確。這也就是剛剛C++ happens-before定義裡的第二點,A inter-thread happens before B

Inter-thread happens before

[Java定義清楚用何種語法能夠建立happens-before的關係,在此先不贅述。
C++定義了五種情況都能夠建立跨thread間的happens-before,如下
1) A synchronizes-with B (A和B有適當的同步)
2) A is dependency-ordered before B (A和B有相依的順序關係)
3) A synchronizes-with some evaluation X, and X is sequenced-before B
4) A is sequenced-before some evaluation X, and X inter-thread happens-before B
5) A inter-thread happens-before some evaluation X, and X inter-thread happens-before B

其中第3, 4, 5點都是遞迴定義,因此我們只關注前兩點,不過再解釋下去會讓篇幅過長,影響閱讀和理解的順暢,目前只要先有個概念就好,我們後續再解釋什麼是Synchoronizes-with和dependency-ordered before。

Reference

 
over 1 year ago

multithread環境下,程式會出問題,往往在於執行順序的不確定性。

我們將從如何定義程式執行的順序開始說起,為了簡單起見,我們先從單執行緒的觀點來看執行順序這件事,其中最關鍵知識就是Sequenced-before,你將會發現就連單執行緒的程式,也可能會產生不確定的執行順序。

Sequenced-before

要了解sequenced-before,首先要了解何謂evaluation(求值)。

Evaluation 求值

所謂求值,其實說穿了就是兩件事情,一個是value computations,對一串運算式計算的結果;另一個是side effect,也就是對物件狀態的修改,像是修改記憶體內變數的值、呼叫library的I/O function之類的。

對於C++來說,語言並沒有定義運算元的求值順序,因此像是f1() + f2() + f3()這種程式,Compiler可以任意決定要先計算哪一個函式,之後再按照加法運算子的left-to-right associativity從左邊加到右邊。

因此計算結果看起來會像(f1() + f2()) + f3(),但執行時f3()可以是第一個、第二個、或是最後才被呼叫。

sequeced-before就是一種對同一個thread下,求值順序關係的描述

  • 如果A is sequenced-before B,代表A的求值會先完成,才進行對B的求值
  • 如果A is not sequenced before B 而且 B is sequenced before A,代表B的求值會先完成,才開始對A的求值。
  • 如果A is not sequenced before B 而且 B is not sequenced before A,代表兩種可能,一種是順序不定,甚至這兩者的求值過程可能會重疊(因為CPU優化指令交錯的關係)或不重疊。

而語言的工作,就是定義一連串關於sequenced-before的Rule,舉例來說:

以下提到的先於、先進行之類的用詞,全部的意思都是sequenced-before,也就是先完成之後才開始進行

  • 上一行的求值(包含value computations和side effect),會先於下一行的求值。(所以你寫的程式會看起來像是上一行的效果發生完,才執行下一行)
  • 運算元的value compuation會先於運算子的value compuation(所以f1() + f2()會先計算完f1()和f2(),才計算兩者加起來的結果),這條規則並不包含side effect
  • i++這類的後置運算子,value computation會先於side effect
  • ++i這類的前置運算子,side effect會先於value computation
  • &&, ||, ,這類的運算子,有著比較特殊的例外,左邊的運算元的evaluation會先於右邊的evaluation。因此i++ && (i+j),右邊的i會是副作用產生後的結果。
  • 對於assignment operator而言(=, +=, -=之類的),會先進行運算元的value computation,之後才是assigment的side effect, 最後是整個assigment expression的value computation。

儘管我們定義許多Evaluation Order的規則,但語言依舊保留一些未定義的行為。

舉例來說,像是經典的未定義行為

i = i++

最後到底i會是什麼,答案沒有人知道,因為如果我們把sequenced-before的關係畫出來的話,如下圖。

把每個求值計算的過程和sequenced-before的關係標出來的話,就會有如下的關係

可以看到問題在於,i++的side effect只sequenced-before i++本身的result,這個side effect可能發生在assignment之前或之後,我們並沒有定義出他們的順序關係,因此讓整行程式產生了不確定的行為。

小補充

sequenced-before 是一種 非對稱性(asymmetric), 遞移性(transitive)的關係
for all a, b, and c in P, we have that:

  • if a < b then ¬ (b < a) (asymmetry)
    • 舉例來說,實數範圍內的小於就是一種asymmetry的關係,因為如果a<b的話,必然not b < a
    • 而實數範圍的小於等於就不是一種asymmetry的關係,因為x <= x,交換過來亦成立
  • if a < b and b < c then a < c (transitivity)
    • 遞移性應該就不需要解釋了

Reference